Дерево

Дано дерево, у вузлах якого розміщені цілі числа. Для кожного внутрішнього вузла потрібно визначити мінімальний модуль різниці чисел у двох різних вершинах його піддерева.

Вхідні дані

Перший рядок містить число вершин у дереві n (1 ≤ n ≤ 40000). У наступних n рядках наведені пари чисел p[i] та v[i] (0 ≤ i < n). Тут p[i] — це номер предка вершини з номером i. Якщо p[i] = -1, то ця вершина є коренем дерева. v[i] — число, записане у вершині (0 ≤ v[i] ≤ 10^6).

Вихідні дані

Виведіть єдине число

за модулем P. i - множина індексів внутрішніх вершин, a[i] - відповіді для них (q = 127, P = 1000000007).

Приклади