D. Кевин и воспоминания о соревнованиях
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кевин раньше попадал в воспоминания Рио, и в воспоминаниях Рио когда-то проводились серии соревнований. Кевин помнит всех участников и все задачи соревнований того времени, но он забыл конкретные раунды, распределение задач и точные рейтинги.

Всего есть $$$ m $$$ задач, при этом $$$ i $$$-я задача имеет сложность $$$ b_i $$$. Пусть каждое соревнование состоит из $$$ k $$$ задач, в результате чего получается $$$ \lfloor \frac{m}{k} \rfloor $$$ соревнований. Это означает, что вы выбираете $$$ \lfloor \frac{m}{k} \rfloor \cdot k $$$ задач для соревнований в любом сочетании, при этом каждая задача выбирается не более одного раза, а оставшиеся $$$m\bmod k$$$ задач остаются неиспользованными. Например, если $$$m = 17$$$ и $$$k = 3$$$, вы должны создать ровно $$$5$$$ соревнований, состоящих из $$$3$$$ задач каждое, и ровно $$$2$$$ задачи останутся неиспользованными.

В соревнованиях участвовало всего $$$ n $$$ участников, причем Кевин был $$$1$$$-м участником. У $$$ i $$$-го участника рейтинг $$$ a_i $$$. Во время соревнований участник решает все задачи, сложность которых не превышает его рейтинг, то есть $$$ i $$$-й участник решает $$$ j $$$-ю задачу тогда и только тогда, когда $$$ a_i \geq b_j $$$. В каждом соревновании ранг Кевина равен одному плюс количеству участников, которые решают больше задач, чем он.

Для каждого $$$ k = 1, 2, \ldots, m $$$ Кевин хочет знать минимальную сумму его рангов по всем $$$ \lfloor \frac{m}{k} \rfloor $$$ соревнованиям. Другими словами, для некоторого значения $$$k$$$, после выбора задач для каждого соревнования, вы вычисляете ранг Кевина в каждом соревновании и суммируете эти ранги по всем $$$ \lfloor \frac{m}{k} \rfloor $$$ соревнованиям. Ваша цель — минимизировать это значение.

Обратите внимание, что соревнования для разных значений $$$k$$$ независимы. Это означает, что для разных значений $$$k$$$ вы можете независимо выбирать распределение задач в соревнованиях.

Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит количество наборов $$$ t $$$ ($$$ 1 \le t \le 5\cdot 10^4 $$$).

Первая строка каждого набора содержит два целых числа $$$ n $$$ и $$$ m $$$ ($$$ 1 \le n, m \leq 3\cdot 10^5 $$$) — количество участников и количество задач.

Вторая строка каждого набора содержит $$$ n $$$ целых чисел $$$ a_1, a_2, \ldots, a_n $$$ ($$$ 0 \le a_i \le 10^9 $$$) — рейтинг каждого участника.

Третья строка каждого набора содержит $$$ m $$$ целых чисел $$$ b_1, b_2, \ldots, b_m $$$ ($$$ 0 \le b_i \le 10^9 $$$) — сложность каждой задачи.

Гарантируется, что сумма $$$ n $$$ и сумма $$$ m $$$ по всем тестам не превышают $$$ 3 \cdot 10^5 $$$.

Выходные данные

Для каждого набора выведите $$$m$$$ целых чисел — минимальную сумму рангов Кевина для каждого $$$ k = 1, 2, \ldots, m$$$.

Пример
Входные данные
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
Выходные данные
7 4 2 3
6 2 1 1 2
7 3 2 1 1 1 1
15 9 5 4 4 4
Примечание

Для первого набора:

Когда $$$k=1$$$, поскольку каждое соревнование содержит только одну задачу, распределение на самом деле уникально. Например, в соревновании, которое включает только третью задачу (которая имеет сложность $$$4$$$), все участники, кроме $$$2$$$-го, могут ее решить. Поскольку никто не решает строго больше задач, чем Кевин, его ранг в этом соревновании равен $$$1$$$. Аналогично, в всех $$$4$$$ соревнованиях ранги Кевина равны $$$1,3,1,2$$$, и сумма равна $$$7$$$.

Когда $$$k=2$$$, один из оптимальных способов — выбрать $$$1$$$-ю и $$$3$$$-ю задачи для формирования одного соревнования, а $$$2$$$-ю и $$$4$$$-ю — для другого. В первом соревновании $$$4$$$ участника соответственно решают $$$2,1,2,2$$$ задачи, поэтому ранг Кевина равен $$$1$$$; во втором они соответственно решают $$$0,0,2,1$$$, поскольку $$$2$$$ участника ($$$3$$$-й и $$$4$$$-й) решают больше задач, чем Кевин, его ранг равен $$$1+2=3$$$. Таким образом, ответ равен $$$1+3=4$$$. Можно доказать, что нет способа достичь меньшей суммы.

Когда $$$k=3$$$, мы можем просто выбрать $$$1$$$-ю, $$$3$$$-ю и $$$4$$$-ю задачи, чтобы сделать соревнование, и ранг Кевина равен $$$2$$$, что является оптимальным.

Когда $$$k=4$$$, поскольку есть только одно соревнование, распределение также уникально, и ранг Кевина равен $$$3$$$.