A93505.长大的树

有一棵以 $1$ 号结点为根的树。一开始树里只有 $1$ 个结点（结点 $1$），并且每个结点的数值都为 $0$。

接下来有 $q$ 个操作，操作有两种：

• $1\ v$：给结点 $v$ 新增一个孩子结点。
  如果当前树里一共有 $sz$ 个结点，那么新结点的编号就是 $sz+1$，它的数值也是 $0$。

• $2\ v\ x$：把 $x$ 加到“以 $v$ 为根的整棵子树”里的每一个结点的数值上。
  （子树的意思是：从 $v$ 出发往下走能到的结点都算，包括 $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$。表示向结点 $v_i$ 添加一个编号为 $sz+1$ 的子结点，其中 $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$。

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

说明/提示

在第一个样例中，最终树及其结点的数值如下图所示：

• 结点的编号是“新建时按顺序编号”的：第一次新增的是 $2$，第二次新增的是 $3$，以此类推。
• 操作 $2\ v\ x$ 会把 $x$ 加到 $v$ 的子树里所有结点（包含 $v$）上。
• 最后按 $1,2,3,\dots,sz$ 的顺序把每个结点的值输出出来。