Minimax Teleportation Time

There are \(N\) worlds (with \(2 \le N \le 2 \times 10^5\)). In world \(i\) (\(1 \le i \le N\)), there is a portal located at coordinates \((i, A_i)\) with \(1 \le A_i \le 10^9\). Each world also contains a cow. At time \(0\) the \(y\)‐coordinates \(A_i\) (for \(1 \le i \le N\)) are all distinct. Then the worlds start falling: world \(i\) falls vertically downward (negative \(y\) direction) at a constant speed of \(i\) units per second, so that at time \(t\) its \(y\) coordinate is \(A_i - i\,t\).

At any moment (which may be a non‐integer time), if two worlds happen to have the same \(y\) coordinate, their portals are synchronized and one of the cows may instantly teleport from one world to the other. For each \(i\), the cow in world \(i\) wishes to travel to world \(Q_i\) (with \(Q_i \neq i\)). Determine, for every cow, the minimum time needed to reach her destination if she moves optimally. If it is impossible for a cow to reach her destination, output \(-1\) instead.

When a teleportation occurs between world \(i\) and world \(j\) (assume \(i A_j\) then the two worlds can never meet. Note that because teleportation is instantaneous, if a cow chooses a sequence of teleportation events, the overall travel time is determined by the latest meeting time along her journey. That is, if she takes a chain of teleportations along worlds \(w_0, w_1, \dots, w_k\) (with \(w_0 = i\) and \(w_k = Q_i\)), and the meeting between \(w_{\ell}\) and \(w_{\ell+1}\) occurs at time \(t_{\ell}\), then her travel time is \(\max_{0 \le \ell < k} t_{\ell}\).

The answer for each cow should be output as a fraction \(\frac{a}{b}\) in simplest terms (i.e. \(a\) and \(b\) are coprime positive integers). If a cow cannot reach her destination, output \(-1\) for that query.

Note: Although there may be many possible teleportation edges between worlds, one may show that there always exists an optimal teleportation chain whose maximum meeting time is equal to the maximum weight on the unique path between the two worlds in a certain spanning tree. In this problem, you may construct the spanning tree as follows:

• For \(i = 1,2,\dots,N\), using a monotonic increasing stack, define \(L_i\) to be the nearest index to the left of \(i\) (if any) such that \(A_{L_i} \le A_i\). If such an index exists, add an undirected edge between \(L_i\) and \(i\) with weight \(\frac{A_i - A_{L_i}}{i - L_i}\).
• For \(i = N,N-1,\dots,1\), similarly define \(R_i\) to be the nearest index to the right of \(i\) such that \(A_i \le A_{R_i}\). If it exists, add an undirected edge between \(i\) and \(R_i\) with weight \(\frac{A_{R_i} - A_i}{R_i - i}\).
• It turns out that the resulting graph is a tree spanning all worlds. Then, for any two worlds, the minimax teleportation time is equal to the maximum edge weight along the unique path between them in this tree.

Your task is to compute, for each cow, the minimax teleportation time from her starting world \(i\) to her destination world \(Q_i\) as described above, and output the result as a simplified fraction.

inputFormat

The first line contains an integer \(N\) (\(2 \le N \le 2 \times 10^5\)).

The second line contains \(N\) integers \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)), representing the initial \(y\)-coordinates of the worlds.

The third line contains \(N\) integers \(Q_1, Q_2, \dots, Q_N\) (each \(Q_i \in \{1,2,\dots,N\}\) and \(Q_i \neq i\)), where \(Q_i\) is the destination world for the cow in world \(i\).

outputFormat

Output \(N\) lines. The \(i\)-th line should contain the minimax time required for the cow in world \(i\) to reach world \(Q_i\), in the form of a simplified fraction \(a/b\) (with \(a\) and \(b\) coprime positive integers), or \(-1\) if it is impossible.

sample

3
1 3 2
3 1 1

1/2
2/1
1/2