Гласа се за границу за пролаз на државно такмичење из атлетике. Сви чланови комисије ће написати на папирић неки број, који ће потом убацити у кутију за гласове. Граница ће се одредити тако што ће се узети медијана свих гласова који су убачени у кутију.

Када је најпопуларнији члан комисије Маркос, познатији као „бог и батина“ дошао да гласа, приметио је да нико не обраћа пажњу на кутију са гласовима. Одлучио је да, након што остатак комисије гласа, дође и провири у кутију, открије шта су остали чланови комисије гласали и затим напише онолико гласова колико је минимално потребно да граница буде баш број \(X\) који је он замислио.

Посматрамо \(Q\) сценарија где је у \(i\)-том сценарију број који је Маркос замислио \(B[i]\). Помозите Маркосу да за сваки сценарио открије колико минимално гласова мора да убаци у кутију за гласове. Гласови који су већ били у кутији су дати низом \(A\), дужине \(N\).

Опис улаза

У првом реду стандардног улаза се налазе два позитивна цела броја \(N\) и \(Q\).

У другом реду се налази низ целих бројева \(A\).

У трећем реду се налази низ целих бројева \(B\).

Опис излаза

За сваки сценарио исписати решење у новом реду.

Пример 1

Улаз

5 3
1 3 5 7 9
5 7 10

Излаз

0
1
5

Објашњења примера

У првом сценарију медијана је већ 5 те је одговор 0. У другом сценарију Маркос може да убаци глас са бројем 8 да би медијана постала 7 те је одговор 1. Коначно, у трећем сценарију, неопходно је да Маркос убаци још најмање пет гласова са бројем 10 или више, да би медијана постала 10, те је одговор 5.

Ограничења

• \(1 \leq N, Q \leq 2*10^5\)
• \(0\leq A[i] \leq 10^9\) за свако \(0 \leq i < N\)
• \(0\leq B[i] \leq 10^9\) за свако \(0 \leq i < Q\)

Тест примери су подељени у четири дисјунктне групе:

• У тестовима вредним 25 поена: \(Q = 1\)
• У тестовима вредним 25 поена: Сваки број \(X\) који је Маркос замислио ће бити већ нечији глас
• У тестовима вредним 25 поена: \(N,Q \leq 1000\)
• У тестовима вредним 25 поена: Без додатних ограничења

Напомена

Нека је дат низ \(A\) са \(N\) чланова. Као медијана овог низа се узима члан који би се нашао у средини када би се низ \(A\) сортирао. Формалније, нека је \(A^\prime\) низ који се добија када се низ \(A\) сортира. Нека је \(A^\prime\) индексиран од \(1\). Медијана низа \(A\) се дефинише као елемент \(A^\prime[\lfloor\dfrac{N}{2}\rfloor + 1]\). На пример, уколико је \(A = [5,7,3,6]\), низ \(A^\prime\) би био \([3,5,6,7]\), а медијана би имала вредност \(6\).