Задача . F. Растущее дерево

В первой строке содержится единственное число \(T\) (\(1 \leq T \leq 10^4\)) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число \(q\) (\(1 \leq q \leq 5 \cdot 10^5\)) — Изначальное количество запросов.

Далее следует \(q\) строк. Далее возможно два случая:

• Первый тип запроса. В \(i\)-й строке дано два целых числа \(t_i\) (\(t_i = 1\)), \(v_i\). Нужно добавить ребёнка с номером \(sz + 1\) к вершине \(v_i\), где \(sz\) — текущий размер дерева. Гарантируется, что \(1 \leq v_i \leq sz\).
• Второй тип запроса. В \(i\)-й строке дано три целых числа \(t_i\) (\(t_i = 2\)), \(v_i\), \(x_i\) (\(-10^9 \leq x_i \leq 10^9\)). Нужно прибавить \(x_i\) ко всем числовым значениям вершин в поддереве вершины \(v_i\). Гарантируется, что \(1 \leq v_i \leq sz\), где \(sz\) — текущий размер дерева.

Гарантируется что сумма \(q\) по всем тестовым наборам не превосходит \(5 \cdot 10^5\).