Có \(N\) thế giới (\(2\le N\le 2\cdot 10^5\)), mỗi thế giới có một cổng dịch chuyển. Ban đầu, thế giới \(i\) (với \(1\le i\le N\)) có tọa độ \(x\) bằng \(i\) và tọa độ \(y\) bằng \(A_i\) (\(1\le A_i\le 10^9\)). Trên mỗi thế giới còn có một con bò. Tại thời điểm \(0\), tất cả các tọa độ \(y\) đều phân biệt và các thế giới bắt đầu rơi: thế giới \(i\) chuyển động liên tục theo chiều âm của trục \(y\) với vận tốc \(i\) đơn vị mỗi giây.

Tại bất kỳ thời điểm nào khi hai thế giới có cùng tọa độ \(y\) (thời điểm này có thể là một số không nguyên), các cổng dịch chuyển sẽ "thẳng hàng", nghĩa là một con bò trên một trong hai thế giới có thể chọn dịch chuyển tức thời sang thế giới còn lại.

Với mỗi \(i\), con bò trên thế giới \(i\) muốn đi đến thế giới \(Q_i\) (\(Q_i\neq i\)). Hãy giúp mỗi con bò xác định hành trình của mình sẽ mất bao lâu nếu nó di chuyển một cách tối ưu.

Mỗi đáp án truy vấn phải là một phân số \(a/b\), trong đó \(a\) và \(b\) là các số nguyên dương nguyên tố cùng nhau, hoặc là \(-1\) nếu hành trình không thể thực hiện được.

Phân nhóm

• Các test từ \(2\) đến \(3\) thỏa mãn \(N\le 100\).
• Các test từ \(4\) đến \(5\) thỏa mãn \(N\le 2000\).
• Các test từ \(6\) đến \(14\) không có ràng buộc bổ sung.

Dữ liệu vào

Dữ liệu vào được đọc từ tệp falling.in.

Dòng đầu tiên chứa một số nguyên \(N\).

Dòng tiếp theo chứa \(N\) số nguyên \(A_1,A_2,\ldots,A_N\), cách nhau bởi dấu cách.

Dòng tiếp theo chứa \(N\) số nguyên \(Q_1,Q_2,\ldots,Q_N\), cách nhau bởi dấu cách.

Dữ liệu ra

Ghi ra tệp falling.out gồm \(N\) dòng; dòng thứ \(i\) chứa thời gian hành trình của con bò \(i\).

Ví dụ

4
3 5 10 2
3 3 2 1

7/2
7/2
5/1
-1

Nguồn

• Kỳ thi: USACO 2020 January Contest, Platinum
• Tên bài: Falling Portals
• Đề bài chính thức: https://usaco.org/index.php?page=viewproblem2&cpid=998
• Tác giả đề: Dhruv Rohatgi