eolymp
bolt
Try our new interface for solving problems
Problems

Дерево

Дерево

Time limit 1 second
Memory limit 122 MiB

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

Input data

В первой строке содержится число вершин в дереве n (1n40000). В следующих n строках пары чисел p_i и v_i (0i < n). p_i — номер предка вершины с номером i, если p_i = -1, то эта единственная вершина является корнем. v_i — число, записанное в вершине (0v_i10^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
Source III International Summer School Programming in Sevastopol 2012