2038: [USACO 2024 February Contest Gold] Problem 3. Quantum Moochanics

In her free time, Bessie likes to dabble in experimental physics. She has recently discovered a pair of new subatomic particles, named mootrinos and antimootrinos. Like standard matter-antimatter pairs, mootrinos and antimootrinos annihilate each other and disappear when they meet. But what makes these particles unique is that they switch their direction of motion (while maintaining 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, with the $i$-th particle located at position $p_i$ ($0\le p_1<\cdots <p_N\le {10}^{18}$). Mootrinos initially move right while antimootrinos initially move left, and the $i$-th particle moves with a constant speed of $s_i$ units per second ($1\le s_i\le {10}^9$).

Bessie makes observations at the following times:

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

This experiment may take an extremely long time to complete, so Bessie would like to first simulate its results. Given the experiment setup, help Bessie determine when (i.e., the observation number) she will observe each particle disappear! It may be shown that all particles will eventually disappear.

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

It is guaranteed that the sum of all $N$ does not exceed $2\cdot {10}^5$.

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

9 9
11 11
1 1
3 3