你在冬天种下了一棵树。这棵树以节点1为根。
一开始，这棵树只有节点1，并且该点的权值为0。之后每一天，这棵树会发生以下两件事中的其中一件：
1、设当前这棵树的节点个数为n，那么节点v会新增一个编号为n+1的叶子节点，节点的权值为0；
2、选择节点v对应的子树，然后这棵子树上所有节点的权值都加上x。
q天过去了，你想要知道这棵树每个节点的权值为多少。
你在冬天种下了一棵树。这棵树以节点1为根。
一开始，这棵树只有节点1，并且该点的权值为0。之后每一天，这棵树会发生以下两件事中的其中一件：
1、设当前这棵树的节点个数为n，那么节点v会新增一个编号为n+1的叶子节点，节点的权值为0；
2、选择节点v对应的子树，然后这棵子树上所有节点的权值都加上x。
q天过去了，你想要知道这棵树每个节点的权值为多少。
第一行一个正整数T，表示有T组数据。
对于每一组数据，第一行一个正整数q，表示一共经过了 q天。之后对于每一天的事件输入一行，格式如下：
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 107 5 8 6 2
1 0 1
4 14 4
对于 30% 的数据，1<=∑q<=10；
对于 60% 的数据，1<=∑q<=100；
对于 80% 的数据，1<=∑q<=10^5；
对于 100% 的数据，，数据保证对于单个测试点 1<=q<=5*10^5 -10^9<=x<=10^9 数据保证对于单个测试点∑q<=5*10^5；