C. Берляндский отбор
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп организует региональные ICPC соревнования в Берляндии. Всего в Берляндии $$$n$$$ университетов, пронумерованных от $$$1$$$ до $$$n$$$. Поликарп знает всех спортивных программистов в регионе. Всего $$$n$$$ студентов: $$$i$$$-й студент учится в университете $$$u_i$$$, а его навык программирования оценивается величиной $$$s_i$$$.

Поликарп сейчас думает над правилами регионального соревнования. В частности, над количеством участников в командах.

Поликарп знает, что если он выберет размер команды, как некоторое целое число $$$k$$$, то каждый университет отправит $$$k$$$ своих самых сильных (с наибольшей величиной навыка $$$s$$$) студентов в первой команде, следующие $$$k$$$ — во второй команде и так далее. Если остается меньше $$$k$$$ студентов, то команду нельзя собрать. Обратите внимание, что некоторые университеты могут отправить ноль команд.

Сила региона определяется, как суммарная величина навыков участников всех команд. Если ни одной команды нет, то сила равна $$$0$$$.

Помогите Поликарпу найти силу региона для каждого $$$k$$$ от $$$1$$$ до $$$n$$$.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных записано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество университетов и количество студентов.

Во второй строке каждого набора входных данных записаны $$$n$$$ целых чисел $$$u_1, u_2, \dots, u_n$$$ ($$$1 \le u_i \le n$$$) — университет, в котором учится $$$i$$$-й студент.

В третьей строке каждого набора входных данных записаны $$$n$$$ целых чисел $$$s_1, s_2, \dots, s_n$$$ ($$$1 \le s_i \le 10^9$$$) — величина навыка программирования $$$i$$$-го студента.

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

На каждый набор входных данных выведите $$$n$$$ целых чисел: силу региона — суммарную величину навыка программирования участников команд — для каждого выбора размера команды $$$k$$$.

Пример
Входные данные
4
7
1 2 1 2 1 2 1
6 8 3 1 5 1 5
10
1 1 1 2 2 2 2 3 3 3
3435 3014 2241 2233 2893 2102 2286 2175 1961 2567
6
3 3 3 3 3 3
5 9 6 7 9 7
1
1
3083
Выходные данные
29 28 26 19 0 0 0 
24907 20705 22805 9514 0 0 0 0 0 0 
43 43 43 32 38 43 
3083
Примечание

В первом наборе входных данных команды университетов для каждого $$$k$$$:

  • $$$k=1$$$:
    • университет $$$1$$$: $$$[6], [5], [5], [3]$$$;
    • университет $$$2$$$: $$$[8], [1], [1]$$$;
  • $$$k=2$$$:
    • университет $$$1$$$: $$$[6, 5], [5, 3]$$$;
    • университет $$$2$$$: $$$[8, 1]$$$;
  • $$$k=3$$$:
    • университет $$$1$$$: $$$[6, 5, 5]$$$;
    • университет $$$2$$$: $$$[8, 1, 1]$$$;
  • $$$k=4$$$:
    • университет $$$1$$$: $$$[6, 5, 5, 3]$$$;