Cho một cây gồm \(n\) đỉnh với đỉnh \(1\) làm gốc. Mỗi \(1 \le i \le n\) có một số nguyên \(c_i\) gọi là màu của đỉnh \(i\). Bạn cần xử lí \(q\) truy vấn thuộc một trong hai dạng sau:

• \(1\) \(u\) \(x\): Thay đổi màu của đỉnh \(u\) thành \(x\), nghĩa là \(c_u = x\).
• \(2\) \(k\) \(u_1\) \(u_2\) \(\dots\) \(u_k\): Xét tập hợp gồm màu của các đỉnh nằm trong các cây con \(u_1, u_2, \dots, u_k\) (các đỉnh xuất hiện nhiều lần được tính nhiều lần). Gọi số lượng phần tử của tập là \(S\), tìm màu vượt trội trong tập này, cụ thể là màu xuất hiện nhiều hơn \(\frac{S}{2}\) lần.

Input

• Dòng đầu gồm hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 10^6\)).
• Dòng thứ hai gồm \(n\) số nguyên dương \(c_1, c_2, \dots, c_n\) (\(1 \le c_i \le n\)).
• Mỗi dòng trong \(n-1\) dòng tiếp theo gồm hai số nguyên \(u\) và \(v\) (\(1 \le u, v \le n\)) thể hiện có cạnh nối giữa \(u\) và \(v\) trên cây.
• Mỗi dòng trong \(q\) dòng tiếp theo là một truy vấn thuộc một trong hai dạng đã mô tả. Dữ liệu đảm bảo tổng các giá trị \(k\) của các truy vấn loại \(2\) không vượt quá \(10^6\).

Output

• Đối với mỗi truy vấn loại \(2\), ghi ra màu vượt trội hoặc -1 nếu không tồn tại.

Scoring

Gọi \(S_k\) là tổng \(k\) qua các truy vấn loại \(2\).

• Subtask \(1\) (\(10\%\) số điểm): \(n, S_k \le 500\), \(c_i \le 10\).
• Subtask \(2\) (\(10\%\) số điểm): \(n, S_k \le 5000\), \(c_i \le 10\).
• Subtask \(3\) (\(20\%\) số điểm): \(n, S_k \le 10^5\), \(c_i \le 10\).
• Subtask \(4\) (\(20\%\) số điểm): \(n, S_k \le 10^5\).
• Subtask \(5\) (\(20\%\) số điểm): không có truy vấn loại \(1\).
• Subtask \(6\) (\(20\%\) số điểm): không có ràng buộc gì thêm.

Example

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

-1
2