Дано корневое дерево с корнем в вершине \(1\). Для любой вершины \(i\) (\(1 < i \leq n\)) в дереве есть ребро, соединяющее вершины \(i\) и \(p_i\) (\(1 \leq p_i < i\)), вес которого равен \(t_i\).
Ирис не знает значений \(t_i\), но она знает, что \(\displaystyle\sum_{i=2}^n t_i = w\) и любое из \(t_i\) является неотрицательным целым числом.
Вершины дерева пронумерованы особым образом: номера вершин в каждом поддереве представляют собой последовательные целые числа. Другими словами, вершины дерева пронумерованы в порядке обхода в глубину.
Дерево на этой картинке удовлетворяет условию. Например, в поддереве вершины \(2\) номера вершин равны \(2, 3, 4, 5\), то есть являются последовательными целыми числами. 
Дерево на этой картинке не удовлетворяет условию, так как в поддереве вершины \(2\) номера вершин \(2\) и \(4\) не являются последовательными целыми числами. Определим \(\operatorname{dist}(u, v)\) как длину простого пути между вершинами \(u\) и \(v\) в дереве.
Далее произойдёт \(n - 1\) событие:
- Ирис сообщают целые числа \(x\) и \(y\), обозначающие, что \(t_x = y\).
После каждого события Ирис хочет знать максимальное возможное значение \(\operatorname{dist}(i, i \bmod n + 1)\) независимо для всех \(i\) (\(1\le i\le n\)). Ей достаточно узнать только сумму этих \(n\) значений. Пожалуйста, помогите Ирис быстро получить ответы.
Обратите внимание, что при вычислении максимально возможных значений \(\operatorname{dist}(i, i \bmod n + 1)\) и \(\operatorname{dist}(j, j \bmod n + 1)\) для \(i \ne j\) неизвестные веса рёбер могут быть разными.
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую \(n-1\) целых числа, каждое из которых представляет ответ после каждого события.
Примечание
В первом наборе входных данных \(\operatorname{dist}(1, 2) = \operatorname{dist}(2, 1) = t_2 = w = 10^{12}\), поэтому \(\operatorname{dist}(1, 2) + \operatorname{dist}(2, 1) = 2 \cdot 10^{12}\)
Во втором наборе входных данных дерево после того, как Ирис узнала все \(t_x\), показано ниже:
\(\operatorname{dist}(1, 2) = t_2\), \(\operatorname{dist}(2, 3) = t_2 + t_3\), \(\operatorname{dist}(3, 4) = t_3 + t_4\), \(\operatorname{dist}(4, 1) = t_4\). После первого события мы узнали, что \(t_2 = 2\), поэтому \(\operatorname{dist}(1, 2) = 2\). В то же время:
- \(\operatorname{dist}(2, 3)\) максимально, если \(t_3 = 7\), \(t_4 = 0\). Тогда \(\operatorname{dist}(2, 3) = 9\).
- \(\operatorname{dist}(3, 4)\) и \(\operatorname{dist}(4, 1)\) максимальны, если \(t_3 = 0\), \(t_4 = 7\). Тогда \(\operatorname{dist}(3, 4) = \operatorname{dist}(4, 1) = 7\).
Таким образом, ответ равен \(2 + 9 + 7 + 7 = 25\).
После второго события мы узнали, что \(t_4 = 4\), тогда \(t_3 = w - t_2 - t_4 = 4\). \(\operatorname{dist}(1, 2) = 2\), \(\operatorname{dist}(2, 3) = 2 + 3 = 5\), \(\operatorname{dist}(3, 4) = 3 + 4 = 7\), \(\operatorname{dist}(4, 1) = 4\). Таким образом, ответ равен \(2 + 5 + 7 + 4 = 18\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 1000000000000
1
2 1000000000000
4 9
1 1 1
2 2
4 4
3 3
6 100
1 2 3 2 1
6 17
3 32
2 4
4 26
5 21
10 511
1 2 2 4 2 1 1 8 8
3 2
6 16
10 256
9 128
2 1
5 8
8 64
4 4
7 32
|
2000000000000
25 18 18
449 302 247 200 200
4585 4473 2681 1567 1454 1322 1094 1022 1022
|