时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
There are N (2≤N≤2⋅105) 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.
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.
输入描述:
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.
输出描述:
Print N lines, the i-th of which contains the journey length for cow i.
示例1
备注:
Test cases 2-3 satisfy N≤100.
Test cases 4-5 satisfy N≤2000.
Test cases 6-14 satisfy no additional constraints.