Однажды мистер Кул создал дерево (неориентированный связный граф без циклов) из n вершин, присвоив каждой вершине i > 1 два числа: pi < i - прямой предок вершины i и wi - вес ребра между вершиной i и pi. Вершина 1 является корнем, поэтому у нее нет предков.

Вы хотели узнать, какое дерево построил мистер Кул, но мистер Кул отказался это сказать, хотя и дал вам наводку:

Он написал следующие числа в одной строке. Так он получил массив b длины 2 * n - 2.

b = [p2, w2, p3, w3, ..., pn-1, wn-1, pn, wn]

Затем он случайно перемешал его. Так он получил массив a, и мистер Кул подарил его Вам. Поскольку восстановить дерево, зная только значения массива a, невозможно, Вам пришлось решить другую задачу.

Назовем дерево k-длинным, если на пути между вершинами 1 и n расположено ровно k ребер.

Назовем дерево k-совершенным, если оно k-длинно и сумма весов ребер на пути между вершиной 1 и вершиной n максимальна среди всех возможных k-длинных деревьев, которые мог построить мистер Кул.

Вам следует вывести сумму весов ребер на пути между вершиной 1 и вершиной n для всех возможных k-совершенных деревьев. Выведите -1, если г-н Кул не может построить некое k-длинное дерево.

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

Первая строка содержит одно целое число n (2 ≤ n ≤ 105) - количество вершин в дереве.

Вторая строка содержит 2 * n - 2 целых чисел a1, a2, ..., a2n-2 (1 ≤ ai ≤ n - 1) - элементы массива a.

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

В одной строке выведите n - 1 целых чисел w1, w2, w3, ..., wn-1 , где wk — сумма весов ребер на пути между вершиной 1 и вершиной n в k-совершенном дереве. Если i-длинного дерева нет, то wi должно быть равно -1.

Пояснение

В первом примере 1-совершенное дерево определяется массивом [1, 2, 1, 2] (т. е. p2 = 1, w2 = 2, p3 = 1, w3 = 2).

2-совершенное дерево определяется массивом [1, 2, 2, 1] (т. е. p2 = 1, w2 = 2, p3 = 2, w3 = 1). Ниже приведены иллюстрации 1-совершенного дерева и 2-совершенного дерева соответственно (путь от вершины 1 до вершины n нарисован жирными линиями):

Во втором примере нет k-совершенных деревьев, которые можно получить перестановкой массива a.

В третьем примере можно получить только 4-совершенное дерево и 5-совершенное дерево. Они определяются массивами [1, 4, 2, 4, 3, 4, 4, 4, 4, 5] и [1, 4, 2, 4, 3, 4, 4, 4, 5, 4] соответственно. Вот иллюстрации к ним: