Falling Portals
There are n worlds, each with a portal. Initially, world i (for 1 ≤ i ≤ n) is at x-coordinate i, and y-coordinate A[i] (1 ≤ A[i] ≤ 10^9). There is also a cow on each world. At time 0, all y-coordinates are distinct and the worlds start falling: world i moves continuously in the negative y direction at a speed of i units per second.
At any time when two worlds are at the same y-coordinate (possibly a fractional time), the portals "align", meaning that a cow on one of the worlds can choose to travel instantaneously to the other world.
For each i, the cow on world i wants to travel to world Q[i] (Q[i] ≠ i). Help each cow determine how long her journey will take, if she travels optimally.
Each query output should be a fraction a / b where a and b are positive and relatively prime integers, or −1 if it the journey is impossible.
Input
The first line contains a single integer n (2 ≤ n ≤ 2 * 10^5). The next line contains n space-separated integers A[1], A[2], ..., A[n]. The next line contains n integers Q[1], Q[2], ..., Q[n].
Output
Print n lines, the i-th of which contains the journey length for cow i.