Problems
Дерево
Дерево
Дано подвешенное дерево, в его узлах помещены целые числа. Для каждого внутреннего узла требуется посчитать минимальный модуль разности чисел в двух различных вершинах поддерева.
Input data
В первой строке содержится число вершин в дереве 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).
Output data
Выведите единственное число
помодулю P. i — множество индексов внутренних вершин, a_i — ответы для них (q = 127, P =1000000007).
Examples
Input example #1
3 -1 1 0 2 0 2
Output example #1
0