以下题面由 AI 翻译。

题目描述

给定一棵根为顶点 $1$ 的有根树，初始时仅有一个顶点。每个顶点的数值初始为 $0$。处理 $q$ 个两种类型的查询：

• 类型1：向顶点 $v$ 添加一个编号为 $sz + 1$ 的子节点，其中 $sz$ 是当前树的大小。新顶点的数值为 $0$。
• 类型2：将 $x$ 加到顶点 $v$ 的子树中所有顶点的数值上。

在处理完所有查询后，输出最终树中每个顶点的数值。

输入格式

第一行包含一个整数 $T$ ($1 \leq T \leq 10^4$) —— 测试用例的数量。每个测试用例的描述如下：

每个测试用例的第一行包含一个整数 $q$ ($1 \leq q \leq 5 \cdot 10^5$) —— 查询的数量。

接下来的 $q$ 行可能为以下两种类型之一：

• 类型1：第 $i$ 行包含两个整数 $t_i$ ($t_i = 1$)、$v_i$。需向顶点 $v_i$ 添加一个编号为 $sz + 1$ 的子节点，其中 $sz$ 是当前树的大小。保证 $1 \leq v_i \leq sz$。
• 类型2：第 $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$。

输出格式

对于每个测试用例，输出最终树中每个顶点的数值。

样例数据

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

提示

对于第一个样例，最终树的结构及数值分配如下图所示：

最终树的结构及数值分配