Cho một cây có ~n~ đỉnh, đỉnh 1 là gốc. Mỗi đỉnh trên đều được tô màu, đỉnh thứ ~i~ được tô bởi màu ~a_i~. Một tập hợp các đỉnh trên được gọi là đẹp nếu có hơn một nửa số đỉnh trong tập được tô bởi cùng một màu.

Có ~m~ truy vấn, mỗi truy vấn thuộc một trong các dạng sau:

• Truy vấn dạng 1 ~u~: kiểm tra xem tập đỉnh gồm các đỉnh nằm trong cây con gốc ~u~ có phải là một tập đẹp hay không;
• Truy vấn dạng 2 ~u~: kiểm tra xem tập đỉnh gồm các đỉnh nằm ngoài cây con gốc ~u~ có phải là một tập đẹp hay không;
• Truy vấn dạng 3 ~u, v~: kiểm tra xem tập đỉnh gồm các đỉnh nằm trên đường đi từ ~u~ tới ~v~ (tính cả ~u~ và ~v~) có phải là một tập đẹp hay không.

Yêu cầu: Với mỗi truy vấn, nếu tập các đỉnh đang xét có quá nửa được tô cùng một màu thì in ra màu đó, ngược lại in ra -1.

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~n, m~ lần lượt là số đỉnh trên cây và số truy vấn;
• Dòng thứ 2 chứa ~n~ số nguyên dương, số thứ ~i~ là ~a_i~ ~(1 \le a_i \le n)~;
• Mỗi dòng trong số ~n - 1~ dòng tiếp theo chứa 2 số nguyên dương ~u, v~ tương ứng với có cạnh nối từ đỉnh ~u~ tới đỉnh ~v~ trên cây;
• ~m~ dòng tiếp theo là các loại truy vấn.

Output

• In ra ~m~ dòng là kết quả của ~m~ truy vấn.

Sample Input 1

8 5
2 3 3 1 2 1 3 1
1 2
1 3
2 4
2 5
3 7
5 6
6 8
1 2
3 4 6
2 6
2 5
3 1 5

Sample Output 1

1
-1
-1
3
2