Quantum Moochanics

In her free time, Bessie likes to dabble in experimental physics. She recently discovered a pair of new subatomic particles, mootrinos and antimootrinos. Like ordinary matter-antimatter pairs, a mootrino and an antimootrino annihilate each other and disappear when they meet. What makes these particles unusual is that each one reverses its direction of motion, keeping the same speed, whenever Bessie looks at them.

For her latest experiment, Bessie has placed an even number $N$ ($2 \le N \le 2 \cdot 10^5$) of these particles in a line. The line starts with a mootrino on the left and then alternates between the two types of particles. The $i$-th particle is at position $p_i$ ($0 \le p_1 \cdots < p_N \le 10^{18}$). Mootrinos initially move right, and antimootrinos initially move left. The $i$-th particle moves at a constant speed of $s_i$ units per second ($1 \le s_i \le 10^9$).

Bessie makes observations at the following times. The first observation is 1 second after the start of the experiment. Each later observation comes 2 seconds after the previous one, then 3 seconds after that, and so on. In general, the $(n+1)$-th observation comes $n+1$ seconds after the $n$-th observation. During each observation, Bessie notes which particles have disappeared.

The experiment may take an extremely long time, so Bessie wants to simulate its results first. Given the setup, determine the observation number at which Bessie sees each particle disappear. It may be shown that all particles eventually disappear.

Each input 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, \dots, p_N$. The third line contains $s_1, \dots, s_N$.

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

For each test case, output the observation number for each particle's disappearance, separated by spaces.