题目描述

你在冬天种下了一棵树。这棵树以节点 1 为根。

一开始，这棵树只有节点 1，并且该点的权值为 0。之后每一天，这棵树会发生以下两件事中的其中一件：

1. 设当前这棵树的节点个数为 n，那么节点 v 会新增一个编号为 n+1 的叶子节点，节点的权值为 0；
2. 选择节点 v 对应的子树，然后这棵子树上所有节点的权值都加上 x。

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 个整数，表示每个节点的权值。行末请不要输出多余空格。

样例输入

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

样例解释

对于第一组数据，最后的树的形态以及权值如下图：

数据范围

• 对于 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