题目描述

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

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

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

输入格式

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

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

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

输出格式

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

输入 #1

7
1 2 1 2 1 2 1
6 8 3 1 5 1 5

输出 #1

29 28 26 19 0 0 0 

输入 #2

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

输出 #2

24907 20705 22805 9514 0 0 0 0 0 0 

数据范围

对于 $50\%$ 的数据，$1 \le n \le 10^2$。 对于 $100\%$ 的数据，$1 \le n \le 2 * 10^5$, $1 \le u_i \le n, 1 \le s_i \le 10^9$。