Поликарп организует региональные ICPC соревнования в Берляндии. Всего в Берляндии \(n\) университетов, пронумерованных от \(1\) до \(n\). Поликарп знает всех спортивных программистов в регионе. Всего \(n\) студентов: \(i\)-й студент учится в университете \(u_i\), а его навык программирования оценивается величиной \(s_i\).
Поликарп сейчас думает над правилами регионального соревнования. В частности, над количеством участников в командах.
Поликарп знает, что если он выберет размер команды, как некоторое целое число \(k\), то каждый университет отправит \(k\) своих самых сильных (с наибольшей величиной навыка \(s\)) студентов в первой команде, следующие \(k\) — во второй команде и так далее. Если остается меньше \(k\) студентов, то команду нельзя собрать. Обратите внимание, что некоторые университеты могут отправить ноль команд.
Сила региона определяется, как суммарная величина навыков участников всех команд. Если ни одной команды нет, то сила равна \(0\).
Помогите Поликарпу найти силу региона для каждого \(k\) от \(1\) до \(n\).
Выходные данные
На каждый набор входных данных выведите \(n\) целых чисел: силу региона — суммарную величину навыка программирования участников команд — для каждого выбора размера команды \(k\).
Примечание
В первом наборе входных данных команды университетов для каждого \(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]\);
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|