Falling Portals

There are N (2\le N\le 2\cdot 10^5) worlds, each with a portal. Initially, world i (for 1 \leq i \leq N) is at x-coordinate i, and y-coordinate A_i (1\le A_i\le 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\neq 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.

SCORING:

Test cases 2-3 satisfy N\le 100.
Test cases 4-5 satisfy N\le 2000.
Test cases 6-14 satisfy no additional constraints.

Problem credits: Dhruv Rohatgi

입력

The first line of input contains a single 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.

출력

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

예제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 \frac{7}{2} worlds 1 and 3 align, so the cow can travel to world 3.

출처

USACO 2020 January Platinum

#4143

Falling Portals 2초 512MB

문제

SCORING:

입력

출력

예제1

출처

역링크 공식 문제집만

#4143 upload -회 done -회 how_to_reg -명

Falling Portals timer 2초 memory 512MB

문제 picture_in_picture_alt text_fields

SCORING:

입력

출력

예제1

출처

역링크 공식 문제집만

#4143

Falling Portals 2초 512MB

문제