Giá trị vượt trội

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. "$1ux$": Thay đổi màu của đỉnh $u$ thành $x$, nghĩa là $c_u=x$;
2. "$2k{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 $S/2$ lần.

Cây con $u$ gồm đỉnh $u$ và mọi hậu duệ của $u$ (với gốc là đỉnh $1$). Nếu một đỉnh nằm trong $m$ cây con trong số $u_1,u_2,\dots ,u_k$ (chẳng hạn khi một đỉnh $u_j$ được liệt kê nhiều lần, hoặc cây con này nằm trong cây con kia) thì màu của nó được đếm $m$ lần, và $S$ là tổng kích thước của $k$ cây con. Một màu xuất hiện đúng $S/2$ lần không phải là màu vượt trội.

Dữ liệu vào

• 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ả: "$1ux$" với $1\le u,x\le n$, hoặc "$2k{u}_1{u}_2\dots u_k$" với $k\ge 1$ và $1\le u_j\le n$.

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$, và có ít nhất một truy vấn loại $2$.

Dữ liệu ra

Đố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, mỗi kết quả trên một dòng.

Ràng buộc

• $1\le n,q\le {10}^6$.
• $1\le c_i\le n$; trong truy vấn loại $1$: $1\le u,x\le n$.
• Gọi $S_k$ là tổng $k$ qua các truy vấn loại $2$: $S_k\le {10}^6$.

Subtasks

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 100000$; $c_i\le 10$.
• Subtask 4 ($20\%$ số điểm): $n,S_k\le 100000$.
• Subtask 5 ($20\%$ số điểm): Không có truy vấn loại $1$.
• Subtask 6 ($20\%$ số điểm): Không có điều kiện gì thêm.

Ở các subtask có điều kiện $c_i\le 10$, mọi màu $x$ trong truy vấn loại $1$ cũng không vượt quá $10$.

Ví dụ