Bessie's Annihilation Experiment

Bessie’s latest experiment in experimental physics involves a line of newly discovered subatomic particles: moo-neutrinos and anti-moo-neutrinos. The particles are arranged in a line with an even number N (2 ≤ N ≤ 2×10⁵) so that the leftmost one is a moo-neutrino and then the two types alternate. The i^th particle starts at position \(p_i\) (with \(0 \le p_1 < p_2 < \cdots < p_N \le 10^{18}\)) and has constant speed \(s_i\) (1 ≤ \(s_i\) ≤ 10⁹). Initially, moo‐neutrinos move to the right while anti‐moo‐neutrinos move to the left.

When a moo‐neutrino and an anti‐moo‐neutrino meet they annihilate each other and disappear. However, these particles have a peculiar property: every time Bessie looks at them, all particles (if they have not yet been annihilated) instantly reverse direction (while keeping their speed unchanged).

Bessie observes the experiment at the following times:

• After 1 second from the start.
• Then 2 seconds after the previous observation.
• Then 3 seconds after the second observation.
• … and so on; the \(k^\text{th}\) observation is taken \((k+1)\) seconds after the \((k-1)^\text{th}\) observation.

Thus, the observations occur at times \(T_k = 1 + 2 + \cdots + (k) = \frac{k(k+1)}{2}\). Note that if particles annihilate during a period between observations, Bessie only notices they are gone at the next observation. In particular, if a collision happens exactly at an observation time, it is recorded in that observation.

Your task is to determine, for each particle, at which observation (i.e. the observation count) Bessie will first note its disappearance. It can be shown that eventually all particles will be annihilated.

Input/Output Formatting: See below.

inputFormat

The input consists of three lines:

1. The first line contains an even integer \(N\) representing the number of particles.
2. The second line contains \(N\) space‐separated integers \(p_1, p_2, \ldots, p_N\) representing the initial positions, in strictly increasing order.
3. The third line contains \(N\) space‐separated integers \(s_1, s_2, \ldots, s_N\) representing the speeds of the particles.

Remember that the leftmost particle (i.e. the first one) is a moo‐neutrino (initially moving to the right) and the particles alternate types thereafter.

outputFormat

Output a single line containing \(N\) space‐separated integers. The \(i^\text{th}\) number should be the observation count at which Bessie first notices that the \(i^\text{th}\) particle has disappeared.

Note: If a particle is involved in a collision exactly at an observation time, then its annihilation is recorded in that observation.

sample

4
0 5 10 12
1 1 1 1

5 5 1 1