给你一棵有根树,根位于顶点 $$$1$$$,最初由单个顶点组成。每个顶点都有一个数值,最初设置为 $$$0$$$。还有两种类型的 $$$q$$$ 查询:
- 第一种类型:将编号为 $$$sz + 1$$$ 的子顶点添加到顶点 $$$v$$$,其中 $$$sz$$$ 是树的当前大小。新顶点的数值将为$$$0$$$。
- 第二种:将$$$x$$$添加到顶点$$$v$$$的子树中所有顶点的数值上。
所有查询结束后,输出最终树中所有顶点的数值。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,在执行所有查询后输出最终树的每个顶点的数值。
示例
输入 #1
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
输出 #1
7 5 8 6 2 1 0 1 4 14 4
注意
在第一种情况下,具有指定数值的最终树将如下所示:
具有指定数值的最终树