D. Pokémon Tazos
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A group of $$$n$$$ friends has gathered to exchange Pokémon tazos. Each of them has brought $$$n_i$$$ identical tazos. Fortunately, each of the $$$n$$$ friends has brought a different type of tazo.

The exchange works as follows:

Initially, all friends have their $$$n_i$$$ tazos in their hands, from there they repeat the following steps until no one has tazos in their hands:

- Among the tazos they have in their hands, they keep the ones they want in their pocket, in the same turn they cannot choose to keep more than one tazo of each type. - The tazos they do not want are given to one of the other friends.

The $$$n$$$ friends want to get the maximum number of tazos, so in each turn they will keep the maximum number of tazos they can. It does not matter if they have repeated tazos in their pocket.

In addition, each one will always give the tazos they have in their hands to their best friend, $$$a_i$$$.

At the end of the exchange, how many tazos does each friend have?

Input

The input starts with an integer $$$t$$$ indicating the number of cases.

Each case starts with a line with an integer $$$n$$$.

The next line contains $$$n$$$ integers $$$n_i$$$ indicating the number of tazos for each friend.

The last line of the case contains $$$n$$$ integers $$$a_i$$$ indicating the best friend of each friend.

Output

For each case, write a line with $$$n$$$ integers, where each integer indicates the number of tazos that each friend ends up with.

Scoring

$$$1 \leq t \leq 100$$$

$$$0 \leq a_i \leq n-1$$$

$$$1 \leq n_i \leq 10^{12}$$$

$$$2 \leq n \leq 10^5$$$

5 Points: $$$n_i \leq 2$$$

11 Points: $$$n,n_i \leq 500$$$

13 Points: $$$n \leq 500$$$

7 Points: For $$$i \gt 0$$$, we have $$$a_i = i-1$$$, and $$$a_0 = n-1$$$

10 Points: For $$$i \gt 0$$$, we have $$$a_i = i-1$$$

13 Points: For $$$i \gt 0$$$, we have $$$a_i \lt i$$$, and $$$a_0 = 1$$$

41 Points: no restrictions

Example
Input
5
3
2 1 2
1 0 1
4
3 4 4 2
3 2 0 1
10
1 2 3 4 5 6 7 8 9 10
9 0 1 2 3 4 5 6 7 8
5
100000000 123456789 987654321 12 3
2 3 0 1 0
5
234125 45234 2345 5623 435
2 0 1 2 3
Output
1 3 1 
3 4 2 4 
10 9 8 7 6 5 4 3 2 1 
543827161 61728401 543827162 61728400 1 
95919 95919 95921 2 1