Дано подвешенное дерево, в его узлах помещены целые числа. Для каждого внутреннего узла требуется посчитать минимальный модуль разности чисел в двух различных вершинах поддерева.
В первой строке содержится число вершин в дереве 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).