John isi renoveaza ferma

Task

John Marston, the classic character from the game Red Dead Redemption, has reunited with Abigail and the two are renovating their farm at Beecher's Hope.

He has $N$ plantations numbered from $1$ to $N$, with $N - 1$ roads between them, in the form of a tree rooted at $1$. On each plantation he has a number of plants, initially $0$ everywhere. Abigail wants to make $Q$ changes to this tree, and she has $2$ kinds of changes:

• 1 x : Node $x$ gets a new child, initialized to $0$ (first $n + 1$ is added, then $n + 2$, $n + 3$, etc.)
• 2 x y : For each node $i$ in the subtree rooted at node $x$, the number of plants in node $i$ is XORed with $y$.

Now the two of them, like your usual farmers, are curious for each plantation $i$, how many other plantations have the same number of plants as it?

Input

On the first line, the number $N$ is given, followed by $N - 1$ lines describing the edges of the tree. Then, $Q$ is given, and the $Q$ operations with the format described in the statement.

Output

The required answers will be displayed, on a single line, for each node, separated by spaces.

Restrictions and specifications

• $1 \leq N \leq 2 \cdot 10^5$;
• $1 \leq Q \leq 2 \cdot 10^5$;
• $Q \leq N \cdot 3$;
• $1 \leq x \leq \text{the number of nodes at any moment}$;
• $1 \leq y \leq 10^9$;
• It is guaranteed that initial edges form a tree.

Subtasks

• For tests worth $10$ points: $N \leq 1\ 000$, each edge is of the form $(i, i + 1)$, there are only operations of type $2$
• For other tests worth another $10$ points: each edge is of the form $(i, i + 1)$, there are only operations of type $2$
• For other tests worth another $20$ points: $N \leq 1\ 000$, there are only operations of type $2$
• For other tests worth another $10$ points: there are only operations of type $2$
• For other tests worth another $50$ points: no other restrictions

Example 1

stdin

5
1 2
1 3
1 4
5 3
4
1 3
2 3 2
2 6 3
1 5

stdout

3 3 1 3 1 0 3

Explanation

After the first operation, the edge $(3, 6)$ is added.

After the second operation, the plantations $3$, $5$, $6$ have the number of plants XORed by $2$, now having $2$ plants.

After the third operation, the plantation $6$ has the number of plants XORed by $3$, now having $1$ plant.

After the fourth operation, the edge $(5, 7)$ is added.

The number of plants in each plantation are, in order:

0 0 2 0 2 1 0

which corresponds to the solution in the output (the plantation $1$ has $3$ other plantations with the same number of plants, the plantation $3$ only one with the same number of plants, etc.).