Sakurako's Test
Contest: Codeforces Round 970 (Div. 3)
Difficulty rating: 2100
Tags: binary search, brute force, greedy, math, number theory

Sakurako will soon take a test. The test can be described as an array of integers $$$n$$$ and a task on it:

Given an integer $$$x$$$, Sakurako can perform the following operation any number of times:

- Choose an integer $$$i$$$ ($$$1\le i\le n$$$) such that $$$a_i\ge x$$$;
- Change the value of $$$a_i$$$ to $$$a_i-x$$$.

Using this operation any number of times, she must find the minimum possible median$$$^{\text{∗}}$$$ of the array $$$a$$$.

Sakurako knows the array but does not know the integer $$$x$$$. Someone let it slip that one of the $$$q$$$ values of $$$x$$$ will be in the next test, so Sakurako is asking you what the answer is for each such $$$x$$$.

Input format:
The first line contains one integer $$$t$$$ ($$$1\le t\le 10^4$$$)  — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1\le n,q\le 10^5$$$)  — the number of elements in the array and the number of queries.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1\le a_i\le n$$$)  — the elements of the array.

The following $$$q$$$ lines each contain one integer $$$x$$$ ($$$1\le x\le n$$$).

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$10^5$$$. The same guarantee applies to the sum of $$$q$$$ across all test cases.

Output format:
For each test case, output $$$q$$$ integers  — the answer for each query.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
2
5 5
1 2 3 4 5
1
2
3
4
5
6 3
1 2 6 4 1 3
2
1
5

Example output:
0 1 1 1 2 
1 0 2

Editorial:
Let's fix one $$$x$$$ and try to solve this task for it. As we know, in $$$0-$$$indexed array median is $$$\lfloor\frac{n}{2}\rfloor$$$ where $$$n$$$ is number of elements in the array, so to find median, we need to find the smallest element which has at least $$$\lfloor\frac{n}{2}\rfloor$$$ elements in the array that is less or equal to it. Also, it is obvious, that we need to decrease all elements till we can, since the least element, the least median of the array is. So, after all operation, we change $$$a_i$$$ to $$$a_i \mod x$$$.
How to find number of $$$i$$$ that $$$a_i\mod x\le m$$$ for some $$$m$$$. In fact, we can try to find number of elements in range $$$[k\cdot x,k\cdot x+m]$$$ for all $$$k$$$, since all this elements will be less then $$$m$$$ if we take it by modulo $$$x$$$. To find number of elements in such range, we can notice that $$$a_i\le n$$$, so we can make prefix sum of counting array (let's call it $$$pref[i]$$$ number of elements less or equal $$$i$$$) and then number of elements in tange $$$[a,b]$$$ will be $$$pref[b]-pref[a-1]$$$. Also, since $$$a_i\le n$$$, $$$k$$$ will be less then $$$\frac{n}{x}$$$, so for fixed $$$x$$$ our solution will work in $$$\frac{n}{x}\cdot log(n)$$$. Let's precompute it for all $$$x$$$ in range $$$[1,n]$$$. Then, it will work in time $$$\sum_{x=1}^{n+1}\frac{n}{x}\cdot log(n)=log(n)\cdot \sum_{x=1}^{n+1}\frac{n}{x} \stackrel{(*)}{=} log(n)\cdot n\cdot log(n)=n\cdot log^2(n)$$$.
$$$(*)$$$ This transition is true because of $$$\sum_{i=1}^{n+1}\frac{n}{x}$$$ is harmonic series. It means, $$$\sum_{i=1}^{n+1}\frac{n}{x}=n\cdot \sum_{i=1}^{n+1}\frac{1}{x}\le n\cdot log(n)$$$.