Имеется n миров, в каждом из которых есть портал. Первоначально мир i (для 1 ≤ i ≤ n) находится в x - координате i и y - координате Ai (1 ≤ Ai ≤ 109). Также в каждом мире есть корова. В момент времени 0 все y - координаты различны, и миры начинают падать: мир i непрерывно движется в отрицательном y направлении со скоростью i единиц в секунду.

В любое время, когда два мира находятся в одной и той же y-координате (возможно в дробное время), порталы "выравниваются". Это означает, что корова в одном из миров может мгновенно переместиться в другой мир.

Для каждого значения i корова в мире i хочет отправиться в мир Qi (Qi ≠ i). Помогите каждой корове определить, сколько времени займет ее путь, если она будет двигаться оптимально.

Каждый ответ на запрос должен быть дробью a / b, где a и b - положительные и взаимно простые целые числа, или -1, если путешествие невозможно.

Входные данные

Первая строка содержит единственное целое число n (2 ≤ n ≤ 2 * 105). Следующая строка содержит n целых чисел A1, A2, ..., An. В следующей строке записано n целых чисел Q1, Q2, ..., Qn.

Выходные данные

Выведите n строк, i - ая из которых содержит длину пути коровы i.