Ở 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 bể 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:

1. Đổ đầy nước vào bể \(v\), khi đó tất cả các bể con, cháu,... của nó sẽ đầy nước.
2. Hút hết nước khỏi bể \(v\), khi đó các bể cha, ông,... của nó đều hết nước.
3. Kiểm 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 đầu tiên chứa số nguyên dương \(n \leq 500000\) là số lượng bể nước
• \(n-1\) dòng tiếp theo mỗi dòng ghi hai số nguyên \(a_i, b_i\) \((1 \leq a_i, b_i \leq n, \ a_i \neq b_i)\) mô tả một đường ống
• Dòng tiếp theo ghi số nguyên dương \(Q \leq 50000\) là số lượng các thao tác.
• \(Q\) dòng tiếp theo, dòng thứ \(i\) tác gồm hai số nguyên \(c_i\) \((1 \leq c_i \leq 3)\) - loại thao tác và \(v_i\) \((1 \leq v_i \leq n)\) - 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 số \(1\) nếu bể là đầy và số \(0\) nếu bể là rỗng.

Example

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

0
0
0
1
0
1
0
1