在一个寒冷的冬天，你在花园中种下了一颗神奇的种子。这种子很快生根发芽，变成了一颗带有一个节点的小树，这个节点编号为1，权值为0。你注意到，随着时间的流逝，这颗小树以不可思议的方式生长和变化。

每天，小树会经历以下两种变化之一：

1. **节点扩展**：从现有的某个节点长出一个新的叶子节点。例如，如果当前树的节点总数为 n，你可以选择树中的任何一个节点 v ，然后在 v 节点上增加一个新的叶子节点，编号为 n+1 ，并且这个新节点的权值初始化为 0 。

2. **权值增加**：给定树中某个节点 v 的整个子树，增加所有节点的权值。也就是说，可以选择树中的任何一个节点 v，并将 v 节点以及其所有子节点的权值同时增加一个值 x 。

随着时间的流逝，你记录下了每天树的变化方式。现在，经过了 Q 天后，你想知道这棵神奇的小树的每个节点的权值是多少。

为了帮助理解这个问题，假设你有 T 组这样的数据需要处理，每组数据描述了小树从一个节点开始，经历 Q 天的变化历程。你需要为每一组数据计算出在这些天之后，小树的每个节点的权值。

第一行一个正整数 T，表示有 T 组数据。

对于每一组数据，第一行一个正整数 Q，表示一共经过了 Q 天。之后对于每一天的事件输入一行，格式如下：

- ```1 v```：表示给节点 v 新增一个编号为 n+1 的叶子节点。输入保证 1 \le v \le n；

- ```2 v x```：表示给节点 v 对应的子树的所有节点的权值都加上 x。输入保证 1 \le v \le n。

对于每一组数据，设这棵树经过 Q 天之后的节点个数为 n，那么输出一行 n 个整数，表示每个节点的权值。行末请不要输出多余空格。

- 对于 30% 的数据，1 \le \sum Q \le 10；

- 对于 60% 的数据，1\le \sum Q \le 100

- 对于 80% 的数据，1\le \sum Q\le 10^5

- 对于 100% 的数据，1\le Q \le 5\times 10^5, -10^9 \le x \le 10^9, 1\le T \le 100，数据保证对于单个测试点 \sum Q \le 5 \times 10^5