[solution] A Growing Tree Solution Codechef

You are given a rooted tree with the root at vertex $1$ , initially consisting of a single vertex. Each vertex has a numerical value, initially set to $0$ . There are also $q$ queries of two types:

The first type: add a child vertex with the number $s z + 1$ to vertex $v$ , where $s z$ is the current size of the tree. The numerical value of the new vertex will be $0$ .
The second type: add $x$ to the numerical values of all vertices in the subtree of vertex $v$ .

After all queries, output the numerical value of all of the vertices in the final tree.

Input

The first line contains a single integer $T$ ( $1 \leq T \leq 10^{4}$ ) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains a single integer $q$ ( $1 \leq q \leq 5 \cdot 10^{5}$ ) — the number of queries.

The following $q$ lines can fall into two cases:

The first type of query: The $i$ -th line contains two integers $t_{i}$ ( $t_{i} = 1$ ), $v_{i}$ . You need to add a child with the number $s z + 1$ to vertex $v_{i}$ , where $s z$ is the current size of the tree. It is guaranteed that $1 \leq v_{i} \leq s z$ .
The second type of query: The $i$ -th line contains three integers $t_{i}$ ( $t_{i} = 2$ ), $v_{i}$ , $x_{i}$ ( $- 10^{9} \leq x_{i} \leq 10^{9}$ ). You need to add $x_{i}$ to all numerical values of vertices in the subtree of $v_{i}$ . It is guaranteed that $1 \leq v_{i} \leq s z$ , where $s z$ is the current size of the tree.

It is guaranteed that the sum of $q$ across all test cases does not exceed $5 \cdot 10^{5}$ .

Output

For each test case, output the numerical value of each vertex of the final tree after all queries have been performed.

Example

input

Copy

2 1 3

1 1

2 2 1

1 1

2 3 2

1 3

2 1 4

1 3

2 3 2

2 1 1

1 1

2 1 -1

1 1

2 1 1

1 1

2 1 1

2 1 3

2 2 10

output

Copy

7 5 8 6 2 
1 0 1 
4 14 4

Note

In the first case, the final tree with the assigned numerical values will look like this:

$\text{[math]}$ The final tree with the assigned numerical values

Leave a Comment Cancel reply