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:
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 ≤ T ≤ 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 ≤ q ≤ 5 · 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 sz + 1 to vertex v_i, where sz is the current size of the tree. It is guaranteed that 1 ≤ v_i ≤ sz. The second type of query: The i-th line contains three integers t_i (t_i = 2), v_i, x_i (-10^9 ≤ x_i ≤ 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 ≤ v_i ≤ sz, where sz is the current size of the tree. It is guaranteed that the sum of q across all test cases does not exceed 5 · 10^5.
Output
For each test case, output the numerical value of each vertex of the final tree after all queries have been performed.
Examples
Note
In the first case, the final tree with the assigned numerical values will look like this: The final tree with the assigned numerical values