Падаючі портали
Маємо n світів, у кожному з яких є портал. Спочатку світ i (для 1 ≤ i ≤ n) розташований на x-координаті i та y-координаті A[i] (1 ≤ A[i] ≤ 10^9). У кожному світі також є корова. На початку, у момент часу 0, всі y-координати різні, і світи починають падати: світ i безперервно рухається вниз по осі y зі швидкістю i одиниць в секунду.
У будь-який момент, коли два світи опиняються на одній і тій самій y-координаті (можливо у дробовий час), їхні портали "вирівнюються". Це означає, що корова з одного світу може миттєво переміститися в інший світ.
Для кожного значення i корова в світі i прагне потрапити в світ Q[i] (Q[i] ≠ i). Допоможіть кожній корові визначити, скільки часу займе її подорож, якщо вона буде рухатися оптимально.
Кожна відповідь на запит повинна бути у вигляді дробу a / b, де a і b - додатні та взаємно прості цілі числа, або -1, якщо подорож неможлива.
Вхідні дані
Перший рядок містить одне ціле число n (2 ≤ n ≤ 2 * 10^5). Другий рядок містить n цілих чисел A[1], A[2], ..., A[n]. Третій рядок містить n цілих чисел Q[1], Q[2], ..., Q[n].
Вихідні дані
Виведіть n рядків, де i-ий рядок містить час подорожі корови i.