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. "1 u x": Thay đổi màu của đỉnh ~u~ thành ~x~, nghĩa là ~c_u = x~;

2. "2 k u1 u2 ... 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 ~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.

Sample Input 1

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

Sample Output 1

-1
2