Дерево

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

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

В первой строке содержится число вершин в дереве 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).

Примеры