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 \ u_1 \ u_2 \ ... \ 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, ..., 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.

Dữ liệu: Vào từ thiết bị vào chuẩn có khuôn dạng:

• 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, ..., 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~.

Kết quả: Ghi ra thiết bị ra chuẩn, đố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.

Ví dụ:

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

Subtask 1 (10 điểm): ~n, S_k \le 500; c_i \le 10~.
Subtask 2 (10 điểm): ~n, S_k \le 5000; c_i \le 10~.
Subtask 3 (20 điểm): ~n, S_k \le 10^5; c_i \le 10~.
Subtask 4 (20 điểm): ~n, S_k \le 10^5~.
Subtask 5 (20 điểm): Không có truy vấn loại ~1~.
Subtask 6 (20 điểm): Không có điều kiện gì thêm.