Nhà khoa học điên Mike đã xây dựng một cây có gốc, gồm \(n\) đỉnh. Mỗi đỉnh là một bể chứa có thể trống hoặc đầy nước.

Các đỉnh của cây được đánh số từ \(1\) đến \(n\) với gốc là đỉnh \(1\). Đối với mỗi đỉnh, các bể chứa của các con nằm bên dưới bể chứa của đỉnh đó, và đỉnh này được kết nối với mỗi đứa con của nó bằng một ống cho phép nước chảy xuống dưới.

Mike muốn thực hiện các thao tác sau với cây:

• 1-Đổ nước vào đỉnh \(v\). Sau đó, đỉnh \(v\) và tất cả các con của nó sẽ được đổ đầy nước.
• 2-Làm cạn nước ở đỉnh \(v\). Sau đó, đỉnh \(v\) và tất cả các tổ tiên của nó sẽ bị làm cạn.
• 3-Xác định xem đỉnh \(v\) hiện tại có đầy nước hay không. Ban đầu, tất cả các đỉnh của cây đều trống rỗng.

Mike đã lập sẵn một danh sách đầy đủ các thao tác mà anh ta muốn thực hiện theo thứ tự. Trước khi thử nghiệm với cây, Mike quyết định chạy danh sách qua một cuộc mô phỏng. Hãy giúp Mike xác định kết quả sau khi thực hiện tất cả các thao tác.

Dữ liệu vào

• Dòng đầu tiên của dữ liệu vào chứa một số nguyên \(n\) \((1 \le n \le 500000)\) - số lượng đỉnh trong cây.
• Mỗi dòng trong số \(n - 1\) dòng tiếp theo chứa hai số nguyên cách nhau bởi dấu cách \(a_i, b_i\) \((1 \le a_i, b_i \le n, a_i \neq b_i)\) - các cạnh của cây.
• Dòng tiếp theo chứa một số nguyên \(q\) \((1 \le q \le 500000)\) - số lượng thao tác cần thực hiện.
• Mỗi dòng trong số \(q\) dòng tiếp theo chứa hai số nguyên cách nhau bởi dấu cách \(c_i\) \((1 \le c_i \le 3)\), \(v_i\) \((1 \le v_i \le n)\), trong đó \(c_i\) là loại thao tác (theo thứ tự đã cho trong đề bài), và \(v_i\) là đỉnh mà thao tác sẽ được thực hiện.

Đảm bảo rằng đồ thị được cung cấp là một cây hợp lệ.

Dữ liệu ra

• Với mỗi truy vấn loại \(3\), hãy in ra số \(1\) trên một dòng riêng nếu đỉnh đó đầy nước, và \(0\) nếu đỉnh đó trống. In các câu trả lời theo thứ tự các truy vấn xuất hiện trong dữ liệu vào.

Input 1

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

Output 1

0
0
0
1
0
1
0
1