QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100
[0]
Statistics

There are N (2N2105) worlds, each with a portal. Initially, world i (for 1iN) is at x-coordinate i, and y-coordinate Ai (1Ai109). 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 (Qii). 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.

Scoring

  • Test cases 2-3 satisfy N100.
  • Test cases 4-5 satisfy N2000.
  • Test cases 6-14 satisfy no additional constraints.

Input Format

The first line of input contains a single integer N.

The next line contains N space-separated integers A1,A2,,AN.

The next line contains N space-separated integers Q1,Q2,,QN.

Output Format

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

Sample Input

4
3 5 10 2
3 3 2 1

Sample Output

7/2
7/2
5/1
-1

Consider the answer for the cow originally on world 2. At time 2 worlds 1 and 2 align, so the cow can travel to world 1. At time 72 worlds 1 and 3 align, so the cow can travel to world 3.

Problem credits: Dhruv Rohatgi