Codeforces Round 907 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

dfs and similar

trees

*2000

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. A Growing Tree

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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 $$$sz + 1$$$ to vertex $$$v$$$, where $$$sz$$$ 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 $$$sz + 1$$$ to vertex $$$v_i$$$, where $$$sz$$$ is the current size of the tree. It is guaranteed that $$$1 \leq v_i \leq sz$$$.
- 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 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 \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

392 1 31 12 2 11 12 3 21 32 1 41 32 3 252 1 11 12 1 -11 12 1 151 11 12 1 12 1 32 2 10

Output

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:

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2023 09:22:00 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|