No submission language available for this problem.

Description

Input

The first line contains a single integer $t$ ($1 \le t \le 10$) — 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 heroes.

The second line contains $n$ integers $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 2 \cdot 10^5$) — the health value of each hero.

The third line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$) — the initial armor value of each hero.

Output

For each testcase, print $n$ integers — the maximum number of points each hero has had over the games played for every possible $x$.

3
3
3 1 2
3 11 5
1
100
200
4
5 9 5 1
9 2 9 10
 
 
 
 
 
 

1 1 1 
20000 
0 4 0 0

Note

In the first testcase, the game for $x = 1$ is played as follows:

• before all rounds: the heroes have $h = [3, 1, 2]$, $a_{\mathit{cur}} = [3, 11, 5]$;
• round $1$: $1$ damage is inflicted on every hero: $h$ remains $[3, 1, 2]$, $a_{\mathit{cur}}$ becomes $[2, 10, 4]$;
• round $2$: $h = [3, 1, 2]$, $a_{\mathit{cur}} = [1, 9, 3]$;
• round $3$: the first hero runs out of armor, so he loses a health point: $h = [2, 1, 2]$, $a_{\mathit{cur}} = [3, 8, 2]$;
• ...
• round $9$: the first hero dies, since his health reaches $0$: $h = [0, 1, 1]$, $a_{\mathit{cur}} = [0, 2, 1]$;
• round $10$: the third hero dies: $h = [0, 1, 0]$, $a_{\mathit{cur}} = [0, 1, 0]$;
• round $11$: the second hero dies: $h = [0, 0, 0]$, $a_{\mathit{cur}} = [0, 0, 0]$.

The second hero was the last hero to die, and he was the only hero alive during one round. Thus, he gets $1$ point for that game.

The game for $x = 4$ is played as follows:

• round $1$: $h = [2, 1, 2]$, $a_{\mathit{cur}} = [3, 7, 1]$;
• round $2$: $h = [1, 1, 1]$, $a_{\mathit{cur}} = [3, 3, 5]$;
• round $3$: $h = [0, 0, 1]$, $a_{\mathit{cur}} = [0, 0, 1]$;
• round $4$: $h = [0, 0, 0]$, $a_{\mathit{cur}} = [0, 0, 0]$;

The third hero was the last hero to die, and he was the only hero alive during one round.