There are n worlds, each with a portal. Initially, world i (for 1 ≤ i ≤ n) is at x-coordinate i, and y-coordinate Ai (1 ≤ Ai ≤ 109). 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 Qi (Qi ≠ 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 * 105). The next line contains n space-separated integers A1, A2, ..., An. The next line contains n integers Q1, Q2, ..., Qn.

Output

Print n lines, the i-th of which contains the journey length for cow i.