You are given a rooted tree with the root at vertex, initially consisting of a single vertex. Each vertex has a numerical value, initially set to . There are also queries of two types:
- The first type: add a child vertex with the number to vertex , where is the current size of the tree. The numerical value of the new vertex will be .
- The second type: add to the numerical values of all vertices in the subtree of vertex .
After all queries, output the numerical value of all of the vertices in the final tree.
The first line contains a single integer( ) — the number of test cases. The descriptions of the test cases follow.
The first line of each test case contains a single integer( ) — the number of queries.
The followinglines can fall into two cases:
- The first type of query: The -th line contains two integers ( ), . You need to add a child with the number to vertex , where is the current size of the tree. It is guaranteed that .
- The second type of query: The -th line contains three integers ( ), , ( ). You need to add to all numerical values of vertices in the subtree of . It is guaranteed that , where is the current size of the tree.
It is guaranteed that the sum ofacross all test cases does not exceed .
For each test case, output the numerical value of each vertex of the final tree after all queries have been performed.
7 5 8 6 2 1 0 1 4 14 4
In the first case, the final tree with the assigned numerical values will look like this: