D. Kevin and Competition Memories
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Kevin used to get into Rio's Memories, and in Rio's Memories, a series of contests was once held. Kevin remembers all the participants and all the contest problems from that time, but he has forgotten the specific rounds, the distribution of problems, and the exact rankings.

There are $$$ m $$$ problems in total, with the $$$ i $$$-th problem having a difficulty of $$$ b_i $$$. Let each contest consist of $$$ k $$$ problems, resulting in a total of $$$ \lfloor \frac{m}{k} \rfloor $$$ contests. This means that you select exactly $$$ \lfloor \frac{m}{k} \rfloor \cdot k $$$ problems for the contests in any combination you want, with each problem being selected at most once, and the remaining $$$m\bmod k$$$ problems are left unused. For example, if $$$m = 17$$$ and $$$k = 3$$$, you should create exactly $$$5$$$ contests consisting of $$$3$$$ problems each, and exactly $$$2$$$ problems will be left unused.

There are $$$ n $$$ participants in the contests, with Kevin being the $$$1$$$-st participant. The $$$ i $$$-th participant has a rating of $$$ a_i $$$. During the contests, each participant solves all problems with a difficulty not exceeding their rating, meaning the $$$ i $$$-th participant solves the $$$ j $$$-th problem if and only if $$$ a_i \geq b_j $$$. In each contest, Kevin's rank is one plus the number of participants who solve more problems than he does.

For each $$$ k = 1, 2, \ldots, m $$$, Kevin wants to know the minimum sum of his ranks across all $$$ \lfloor \frac{m}{k} \rfloor $$$ contests. In other words, for some value of $$$k$$$, after selecting the problems for each contest, you calculate the rank of Kevin in each contest and sum up these ranks over all $$$ \lfloor \frac{m}{k} \rfloor $$$ contests. Your goal is to minimize this value.

Note that contests for different values of $$$k$$$ are independent. It means that for different values of $$$k$$$, you can select the distribution of problems into the contests independently.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$ t $$$ ($$$ 1 \le t \le 5\cdot 10^4 $$$).

The first line of each test case contains two integers $$$ n $$$ and $$$ m $$$ ($$$ 1 \le n, m \leq 3\cdot 10^5 $$$) — the number of participants and the number of problems.

The second line of each test case contains $$$ n $$$ integers $$$ a_1, a_2, \ldots, a_n $$$ ($$$ 0 \le a_i \le 10^9 $$$) — the rating of each participant.

The third line of each test case contains $$$ m $$$ integers $$$ b_1, b_2, \ldots, b_m $$$ ($$$ 0 \le b_i \le 10^9 $$$) — the difficulty of each problem.

It is guaranteed that both the sum of $$$ n $$$ and the sum of $$$ m $$$ over all test cases do not exceed $$$ 3 \cdot 10^5 $$$.

Output

For each test case, output $$$m$$$ integers — the minimum sum of Kevin's ranks for each $$$ k = 1, 2, \ldots, m$$$.

Example
Input
4
4 4
4 3 7 5
2 5 4 6
5 5
5 0 4 8 6
1 3 9 2 7
6 7
1 1 4 5 1 4
1 9 1 9 8 1 0
7 6
1 9 1 9 8 1 0
1 1 4 5 1 4
Output
7 4 2 3
6 2 1 1 2
7 3 2 1 1 1 1
15 9 5 4 4 4
Note

For the first test case:

When $$$k=1$$$, since each contest only contains one problem, the distribution is in fact unique. For example, in the contest which only includes the third problem (which has a difficulty of $$$4$$$), all participants except the $$$2$$$-nd can solve it. Since no one solves strictly more problems than Kevin, his ranking in this contest is $$$1$$$. Similarly, in all $$$4$$$ contests, Kevin's rankings are $$$1,3,1,2$$$, and the sum is $$$7$$$.

When $$$k=2$$$, one optimal way is to choose the $$$1$$$-st and the $$$3$$$-rd problem to form a contest, while the $$$2$$$-nd and $$$4$$$-th for another. In the former contest, $$$4$$$ participants respectively solve $$$2,1,2,2$$$ problems, so Kevin's ranking is $$$1$$$; in the latter one, they respectively solve $$$0,0,2,1$$$, since there are $$$2$$$ participants ($$$3$$$-rd and $$$4$$$-th) solve more problems than Kevin, his ranking is $$$1+2=3$$$. Thus the answer is $$$1+3=4$$$. It can be proven that there's no way to achieve a lower sum.

When $$$k=3$$$, we can simply choose the $$$1$$$-st, the $$$3$$$-rd, and the $$$4$$$-th problem to make a contest, and Kevin has a ranking of $$$2$$$, which is optimal.

When $$$k=4$$$, since there's only one contest, the distribution is also unique, and Kevin's ranking is $$$3$$$.