Ở một vùng núi người ta xây dựng một hệ thống các bể nước được nối với nhau bởi các đường ống nước tạo thành một cấu trúc hình cây. Bể nước số 1 ở vị trí cao nhất trên sườn núi và các đường ống đều nối từ một bể cao hơn đến thấp hơn. Như vậy mỗi bể nước đều nối với một bể cao hơn nó (trừ bể 1) và nối với một số bể khác có độ cao bé hơn nó (gọi là bể con của bể này). Tất nhiên nước luôn chảy từ một bể xuống các bể con của nó.

Hệ thống các bể nước được vận hành bởi ba thao tác sau:

• Đổ đầy nước vào bể v, khi đó tất cả các bể con, cháu, … của nó sẽ đầy nước

• Hút hết nước khỏi bể v, khi đó các bể cha, ông, … của nó đều hết nước

• Kiểm tra bể v đang ở trạng thái đầy nước hay hết nước

Lúc đầu tất cả các bể là rỗng.

Cho một dãy các thao tác theo thứ tự. Hãy cho câu trả lời của các thao tác thuộc loại thứ 3.

Input:

• Dòng 1: chứa số nguyên dương N ( 1 ≤ N ≤ 5.105) là số lượng bể nước

• N – 1¬ dòng tiếp theo, dòng thứ i chứa hai số a[i],b[i] (1≤a[i],b[i]≤ n,a[i]≠ b[i]) mô tả một đường ống .

• Dòng tiếp theo chứa số nguyên dương Q ≤ 50000 là số lượng các thao tác.

• Q dòng tiếp theo, dòng thứ i chứa 2 số nguyên c[i] (1 ≤ c[i] ≤ 3) và v[i] ( 1 ≤ v[i] ≤ n) – với c[i] là loại thao tác và v[i] là số hiệu bể thực hiện thao tác.

Output:

Với các thao tác loại 3 (theo thứ tự) in ra số 1 nếu bể là đầy nước và số 0 nếu là bể rỗng.

Sample Input

5
1 2
5 1
2 3
4 2
12
1 1
2 3
3 1
3 2
3 3
3 4
1 2
2 4
3 1
3 3
3 4
3 5

Sample Output

0
0
0
1
0
1
0
1