Имеется \(N\) (\(2\le N\le 2\cdot 10^5\)) миров, каждый с порталом.
Изначально, мир \(i\) (for \(1 \leq i \leq N\)) имеет \(x\)-координату \(i\),
и \(y\)-координату \(A_i\) (\(1\le A_i\le 10^9\)). В каждом мире есть по одной
корове. В момент времени \(0\), все \(y\)-координаты различны и все миры начинают
падать. Мир \(i\) двигается непрерывно в отрицательном направлении координаты \(y\)
со скоростью \(i\) единиц в секунду.
В любой момент времени, когда два мира находятся на одной и той же
\(y\)-координате (возможно в дробное время), порталы "выравниваются".
Это означает, что корова из одного из этих миров, может используя эти порталы
мгновенно перебраться в другой мир.
Для каждого \(i\) корова из мира \(i\) хочет перебраться в мир \(Q_i\) (\(Q_i\neq i\)).
Определите для каждой коровы, сколько времени ей понадобиться, чтобы перебраться
в желаемый мир, если она будет путешествовать оптимально.
Ответ на каждый запрос необходимо вывести в виде дроби \(a/b\), где \(a\) и \(b\)
положительные и взаимно простые целые числа. Выведите \(-1\) если путешествие
невозможно.
ОЦЕНИВАНИЕ:
- В тестах 2-3 \(N\le 100.\)
- В тестах 4-5 \(N\le 2000.\)
- В тестах 6-14 нет дополнительных ограничений.
ФОРМАТ ВВОДА (файл falling.in):
Первая строка ввода должна содержать одно целое число
\(N.\)
Следующая строка содержит \(N\) разделённых одиночными пробелами целых числе \(A_1,A_2,\ldots,A_N.\)
Следующая строка содержит \(N\) разделённых одиночными пробелами целых чисел \(Q_1,Q_2,\ldots,Q_N.\)
ФОРМАТ ВЫВОДА (файл falling.out):
Выведите \(N\) строк, \(i\)-th из которых содержит длину пути для коровы \(i.\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 5 10 2
3 3 2 1
|
7/2
7/2
5/1
-1
|