Дано корневое дерево с корнем в вершине \(1\), изначально состоящее из одной вершины. У каждой вершины есть числовое значение, изначально равное \(0\). Так же есть \(q\) запросов двух типов:
После всех запросов нужно для каждой вершины вывести его итоговое числовое значение.
В первой строке содержится единственное число \(T\) (\(1 \leq T \leq 10^4\)) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число \(q\) (\(1 \leq q \leq 5 \cdot 10^5\)) — Изначальное количество запросов.
Далее следует \(q\) строк. Далее возможно два случая:
Гарантируется что сумма \(q\) по всем тестовым наборам не превосходит \(5 \cdot 10^5\).
После всех запросов выведите числовые значения каждой вершины конечного дерева.
В первом примере итоговое дерево с числовыми значениями будет выглядеть так:
3 9 2 1 3 1 1 2 2 1 1 1 2 3 2 1 3 2 1 4 1 3 2 3 2 5 2 1 1 1 1 2 1 -1 1 1 2 1 1 5 1 1 1 1 2 1 1 2 1 3 2 2 10
7 5 8 6 2 1 0 1 4 14 4
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач