Water Tree

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem

Initially every vertex is empty. There are three operations:

• Fill a vertex and every vertex in its subtree.
• Empty a vertex and every ancestor of that vertex.
• Query whether a vertex is currently full.

The tree is rooted at vertex 1.

Input

The first line contains $n$. The next $n-1$ lines contain the tree edges. The next line contains $q$. Each of the next $q$ lines contains type v, where $type\in\{1,2,3\}$:

• 1 v: fill the subtree of $v$.
• 2 v: empty $v$ and all its ancestors.
• 3 v: query the state of $v$.

Output

For every operation of type 3, print 1 if vertex $v$ is full, otherwise print 0.

Subtasks

Subtask 1 (20%)

• The tree size and number of operations are at most 20.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• The tree size and number of operations are at most 2000.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le5\cdot10^5$.

Example

Input

1
6
2 1
1 1
1 1
3 1
3 1
2 1

Output

1
1

Explanation

After the fill operations, vertex 1 is full, so both type-3 queries print 1. The final type-2 operation happens after those queries.