Cho một cây có \(n\) đỉnh đánh số từ \(1\) đến \(n\) và đỉ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à đep 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ó \(q\) 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\), truy vấn này 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\), truy vấn này 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\), truy vấn này kiểm tra xem tập đỉnh gồm các đỉnh nằm trên đường đi đơn từ \(u\) tới \(v\) (tính cả \(u\) và \(v\)) có phải là một tập đẹp hay không.

Input

• Dòng đầu tiên chứa số nguyên dương \(n, q\) \((1 \leq n, q \leq 50000)\) là số đỉnh của cây và số lượng truy vấn.
• Dòng thứ hai chứa \(n\) số, số thứ \(i\) là \(a_{i}\) mô tả màu sắc của đỉnh \(i\) \((1 \leq a_{i} \leq n)\).
• \(n − 1\) dòng tiếp theo, mối dòng chứa hai số nguyên dương \(u, v\) \((1 \leq u, v \leq n)\) mô tả cạnh nối hai đỉnh \(u\) và \(v\).
• Tiếp theo gồm có \(q\) dòng mô tả các truy vấn. Các truy vấn thuộc \(1\) trong \(3\) dạng \(1\) \(u\), \(2\) \(u\) hoặc \(3\) \(u\) \(v\).

Output

• Ghi ra \(q\) dòng, mỗi dòng chứa một số nguyên là kết quả của \(q\) truy vấn. Nếu truy vấn đang xét có quá nửa số đỉnh được tô cùng màu, in ra giá trị của màu đó. Ngược lại, in ra \(−1\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1 \leq n, q \leq 2 000\).
• Subtask \(2\) (\(20\%\) số điểm): mỗi đỉnh có tối đa \(2\) cạnh nối trực tiếp.
• Subtask \(3\) (\(20\%\) số điểm): \(1 \leq a_{i} \leq 2\)
• Subtask \(4\) (\(20\%\) số điểm): không có truy vấn loại \(3\).
• Subtask \(5\) (\(20\%\) số điểm): không có ràng buộc nào thêm.

Example

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

1
-1
-1
3
2