Polycarp 是 Berland ICPC 区域活动的组织者。伯兰有 $$$n$$$ 大学,编号从 $$$1$$$ 到 $$$n$$$。波利卡普认识该地区所有有竞争力的程序员。有 $$$n$$$ 个学生:第 $$$i$$$ 个学生就读于大学 $$$u_i$$$,并且具有编程技能 $$$s_i$$$。
坡旅甲现在必须决定规则。特别是团队成员的数量。
Polycarp 知道,如果他选择团队规模为某个整数 $$$k$$$,则每所大学都会将其 $$$k$$$ 最强(具有最高编程技能 $$$s$$$)的学生发送到第一团队,接下来的 $$$k$$$ 最强学生发送到第二团队,依此类推。如果剩下的学生少于$$$k$$$,则无法组建团队。请注意,可能有些大学派出零支球队。
该地区的实力是所有在场队伍成员技能的总和。如果没有队伍在场,则实力为$$$0$$$。
帮助 Polycarp 找出 $$$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$$$ 的选择。
示例
输入 #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
输出 #1
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]$$$;