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

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

В первой строке содержится число вершин в дереве n (1 ≤ n ≤ 40000). В следующих n строках пары чисел pi и vi (0 ≤ i < n). pi — номер предка вершины с номером i, если pi= -1, то эта единственная вершина является корнем. vi — число, записанное в вершине (0 ≤ vi ≤ 106).

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

Выведите единственное число

по модулю P. i - множество индексов внутренних вершин, ai - ответы для них (q = 127, P = 1000000007).