У Мити есть корневое дерево из $$$n$$$ вершин, пронумерованных от $$$1$$$ до $$$n$$$, причем корень дерева имеет номер $$$1$$$. В каждой его вершине $$$v$$$ было записано целое число $$$a_v \ge 0$$$. Для каждой вершины $$$v$$$ Митя вычислил величину $$$s_v$$$: сумму чисел, записанных на пути от вершины $$$v$$$ до корня, а также $$$h_v$$$ — глубину вершины $$$v$$$, то есть количество вершин на пути от вершины $$$v$$$ до корня (таким образом, $$$s_1=a_1$$$, $$$h_1=1$$$).

После этого Митя уничтожил исходные значения $$$a_v$$$. К сожалению, он также случайно уничтожил все значения $$$s_v$$$ для вершин, находящихся на четной глубине (то есть тех, для которых $$$h_v$$$ является четным). Ваша задача состоит в том, чтобы восстановить значения $$$a_v$$$ для каждой из вершин либо определить, что это невозможно. Среди возможных вариантов нужно выбрать тот, при котором сумма значений $$$a_v$$$ во всем дереве является минимально возможной.