Berland Regional

Description:

Input:

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of universities and the number of students.

The second line of each testcase contains $$$n$$$ integers $$$u_1, u_2, \dots, u_n$$$ ($$$1 \le u_i \le n$$$) — the university the $$$i$$$-th student is enrolled at.

The third line of each testcase contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ ($$$1 \le s_i \le 10^9$$$) — the programming skill of the $$$i$$$-th student.

The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output:

For each testcase print $$$n$$$ integers: the strength of the region — the total skill of the members of the present teams — for each choice of team size $$$k$$$.

Sample Input:

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

Sample Output:

29 28 26 19 0 0 0 
24907 20705 22805 9514 0 0 0 0 0 0 
43 43 43 32 38 43 
3083 

Note:

In the first testcase the teams from each university for each $$$k$$$ are:

• $$$k=1$$$:
  • university $$$1$$$: $$$[6], [5], [5], [3]$$$;
  • university $$$2$$$: $$$[8], [1], [1]$$$;
• $$$k=2$$$:
  • university $$$1$$$: $$$[6, 5], [5, 3]$$$;
  • university $$$2$$$: $$$[8, 1]$$$;
• $$$k=3$$$:
  • university $$$1$$$: $$$[6, 5, 5]$$$;
  • university $$$2$$$: $$$[8, 1, 1]$$$;
• $$$k=4$$$:
  • university $$$1$$$: $$$[6, 5, 5, 3]$$$;