Problem Description

During her spare time, Bessie enjoys experimenting with experimental physics. She has recently discovered a pair of new subatomic particles, named Moo-neutrinos and Anti-Moo-neutrinos. Similar to standard matter-antimatter pairs, Moo-neutrinos and Anti-Moo-neutrinos annihilate and disappear when they meet. However, these particles have a unique characteristic: whenever Bessie looks at them, they change their direction of motion (while maintaining the same speed).

In her latest experiment, Bessie arranged an even number $N$ ($2 \le N \le 2 \cdot 10^5$) of these particles in a row. The row starts with a Moo-neutrino, alternating between the two types of particles, with the $i$-th particle located at position $p_i$ ($0 \le p_1 < \cdots < p_N \le 10^{18}$). Initially, Moo-neutrinos move rightward and Anti-Moo-neutrinos move leftward, with the $i$-th particle moving at a constant speed of $s_i$ units per second ($1 \le s_i \le 10^9$).

Bessie conducts observations at the following times:

• First, $1$ second after the experiment starts.
• Then, $2$ seconds after the first observation.
• Then, $3$ seconds after the second observation.
• $\ldots \ldots$
• Then, $n+1$ seconds after the $n$-th observation.

During each observation, Bessie records which particles have disappeared.

This experiment may take a very long time to complete, so Bessie wants to simulate its results first. Given the experimental setup, help Bessie determine when (i.e., the number of observations) she will observe each particle to disappear! It can be proven that all particles will eventually disappear.

Input Format

Each test file contains $T$ ($1 \le T \le 10$) independent test cases.

Each test case consists of three lines. The first line contains $N$, the second line contains $p_1, \ldots, p_N$, and the third line contains $s_1, \ldots, s_N$.

The input guarantees that the sum of all $N$ does not exceed $2 \cdot 10^5$.

Output Format

For each test case, output the number of observations when each particle disappears, separated by spaces.

Sample Input and Output

Input Sample #1

4
2
1 11
1 1
2
1 12
1 1
2
1 11
4 6
2
1 11
4 5

Output Sample #1

9 9
11 11
1 1
3 3

Input Sample #2

2
4
1 3 5 8
1 1 1 1
4
1 4 5 8
1 1 1 1

Output Sample #2

1 1 3 3
7 2 2 7

Notes/Hints

Sample Explanation 1

For the first test case, Bessie observes the following during the first $8$ observations:

• The Moo-neutrino (initially moving rightward) appears at positions $2 \to 0 \to 3 \to -1 \to 4 \to -2 \to 5 \to -3$.
• The Anti-Moo-neutrino (initially moving leftward) appears at positions $10 \to 12 \to 9 \to 13 \to 8 \to 14 \to 7 \to 15$.

Then, exactly at the $9$th observation, the two particles meet and annihilate at position $6$.

For the second test case, the initial position of the Anti-Moo-neutrino is $1$ unit further to the right, causing the two particles to meet at position $6.5$ half a second before the $11$th observation.

Note that we only care about the number of observations, not the time or position.

Sample Explanation 2

For the first test case:

• The two leftmost particles meet exactly at position $2$ during the $1$st observation.
• The two rightmost particles meet at position $6.5$ half a second before the $3$rd observation.

Test Case Properties

• Test point $3$: $N = 2$.
• Test point $4$: $N \le 2000$, and for all particles, $p_i \le 10^4$.
• Test point $5-7$: $N \le 2000$.
• Test point $8-12$: No additional restrictions.

见题面 Input 部分

见题面 Output 部分