题目描述

你是一个地区$\red{ICPC}$的特派员，这个地区的$\red{ICPC}$是组队制，每个队伍有$\red{k}$个人。这个地区有$\red{n}$所学 校和$\red{n}$个人，每个人有一个水平和一个学籍所在学校。

学校会将该学校水平前$\red{k}$ 的人组为一个队伍。然后再将剩余人中水平前$\red{k}$的人组为一个队伍，直到剩下 的人不足$\red{k}$个。某个地区$\red{ICPC}$的精彩程度为所有参赛人的水平之和。

你需要计算分别当$\red{k=1,2,3...n-1,n}$时，$\red{ICPC}$的精彩程度。

输入格式

第一行一个整数$\red{n}$表示参赛选手和学校和数量。

接下来一行$\red{n}$个整数$\red{u_1,u_2,...,u_n}$表示第$\red{i}$名选手学籍所在学校。

接下来一行$\red{n}$个整数$\red{s_1,s_2,...,s_n}$表示第$\red{i}$名选手的水平值。

输出格式

$\red{k}$行每行一个整数，表示当$\red{k=1,2,3...n-1,n}$时，$\red{ICPC}$的精彩程度。

样例

输入样例

10
1 1 1 2 2 2 2 3 3 3
3435 3014 2241 2233 2893 2102 2286 2175 1961 2567

输出样例

24907 20705 22805 9514 0 0 0 0 0 0

提示

对于$\red{50\%}$的数据，$\red{1<=n<=10^2}$。

对于$\red{100\%}$的数据，$\red{1<=n<=2\times 10^5,1<=u_i<=n,1<=s_i<=10^9}$。