该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

33DAI 得到了一棵有根树，根是 $1$ 号点，一开始树上只有一个 $1$ 号点。每个点上写着一个整数，一开始全都是 $0$。

接下来 33DAI 要依次执行 $q$ 次操作，操作有两种：

• 1 v：给 $v$ 号点添加一个儿子。记操作前树的大小为 $sz$，则这个新点的编号是 $sz + 1$，它上面写的数是 $0$。
• 2 v x：把 $v$ 号点当前的子树（$v$ 自己以及此时已经存在的所有后代）里每个点上的数都加上 $x$。

新出现的点上的数是 $0$，它不会被之前执行过的操作二影响；一次操作二也只影响它执行时已经存在的点。

所有操作执行完之后，33DAI 想知道最终树中每个点上的数。

输入格式

从文件 grow.in 读入数据。

第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试用例组数。

接下来依次给出 $T$ 组测试用例，每组测试用例的格式为：

第一行包含一个整数 $q$（$1 \le q \le 5 \times 10^5$），表示操作次数。

接下来 $q$ 行，每行描述一次操作，格式为下列两种之一（含义见题目描述）：

• 1 v；
• 2 v x。

输出格式

输出到文件 grow.out。

对每组测试用例输出一行：这一组操作全部执行完之后，设树的大小为 $n$，则按编号从小到大输出 $1, 2, \dots, n$ 号点上的数，相邻两个数之间用一个空格分隔。

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

样例 1 解释

第一组测试用例中，$9$ 次操作依次为：

1. 2 1 3：只有 $1$ 号点，它加上 $3$；
2. 1 1：给 $1$ 号点添加儿子，新点是 $2$ 号点，它的数是 $0$；
3. 2 2 1：$2$ 号点的子树只有它自己，加上 $1$；
4. 1 1：给 $1$ 号点添加儿子，新点是 $3$ 号点，它的数是 $0$；
5. 2 3 2：$3$ 号点的子树只有它自己，加上 $2$；
6. 1 3：给 $3$ 号点添加儿子，新点是 $4$ 号点，它的数是 $0$；
7. 2 1 4：$1$ 号点的子树是全部 $4$ 个点，都加上 $4$；
8. 1 3：给 $3$ 号点添加儿子，新点是 $5$ 号点，它的数是 $0$；
9. 2 3 2：$3$ 号点的子树是 $3, 4, 5$ 号点，都加上 $2$。

于是 $1$ 号点上的数是 $3 + 4 = 7$，$2$ 号点上的数是 $0 + 1 + 4 = 5$，$3$ 号点上的数是 $0 + 2 + 4 + 2 = 8$，$4$ 号点上的数是 $0 + 4 + 2 = 6$，$5$ 号点上的数是 $0 + 2 = 2$，按编号输出就是 7 5 8 6 2。

第二组测试用例中，$1$ 号点上数的变化依次为 $+1$、$-1$、$+1$，合计 $1$；$2$ 号点是在第二次操作时出现的，它出现之前的加值操作都不算在它头上，它只经历最后一次 $+1$，所以 $2$ 号点是 $1$、$3$ 号点是 $0$，最终输出 1 0 1。

第三组测试用例中，两次 1 1 让 $2$ 号点与 $3$ 号点都成为 $1$ 号点的儿子；前两次 2 1 分别给 $1$ 号点的子树加上 $1$ 与 $3$，两次操作时 $2, 3$ 号点都已经存在，所以它们各得到 $1 + 3 = 4$，$1$ 号点是 $0 + 1 + 3 = 4$；最后的 2 2 10 只加给 $2$ 号点的子树，于是 $2$ 号点上的数是 $4 + 10 = 14$，$3$ 号点是 $4$，按编号输出就是 4 14 4。

样例 2

见 grow2.in 与 grow2.ans。

样例 3

见 grow3.in 与 grow3.ans。

数据范围

对于所有测试数据，保证：

• $1 \le T \le 10^4$；
• $1 \le q \le 5 \times 10^5$；
• 每个测试用例中，执行每次操作前 $1 \le v \le sz$，其中 $sz$ 是当时树的大小；
• 操作二中的 $x$ 满足 $-10^9 \le x \le 10^9$；
• 所有测试用例的 $q$ 之和不超过 $5 \times 10^5$。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。