Description

There are $N$ worlds ($2 \leq N \leq 2 \times 10^5$), and each world has a portal. Initially, world $i$ (for $1 \leq i \leq N$) is at $x$-coordinate $i$ and $y$-coordinate $A_i$ ($1 \leq A_i \leq 10^9$). Each world also contains a cow. At time $0$, all $y$-coordinates are distinct, and then the worlds begin to fall: world $i$ moves along the negative $y$-axis at a speed of $i$ units per second.

At any time, if two worlds have the same $y$-coordinate at some moment (possibly at a non-integer time), their portals will “synchronize”, allowing a cow in one world to choose to instantly teleport to the other world.

For each $i$, the cow in world $i$ wants to go to world $Q_i$ ($Q_i \neq i$). Help each cow compute how much time it takes if she moves in the best possible way.

Each query should be output as a fraction $a/b$, where $a$ and $b$ are coprime positive integers, or $-1$ if it is impossible to reach.

Input Format

The first line contains an integer $N$.

The next line contains $N$ space-separated integers $A_1, A_2, \ldots, A_N$.

The next line contains $N$ space-separated integers $Q_1, Q_2, \ldots, Q_N$.

Output Format

Output $N$ lines. The $i$-th line contains the travel time for cow $i$.

4
3 5 10 2
3 3 2 1

7/2
7/2
5/1
-1

Hint

Sample Explanation

Consider the answer for the cow originally in world $2$. At time $2$, worlds $1$ and $2$ synchronize, so the cow can go to world $1$. At time $\frac{7}{2}$, worlds $1$ and $3$ synchronize, so the cow can go to world $3$.

Subtasks

• Test points $2 \sim 3$ satisfy $N \leq 100$.
• Test points $4 \sim 5$ satisfy $N \leq 2000$.
• Test points $6 \sim 14$ have no additional constraints.

Translated by ChatGPT 5