У Ксоні є кореневе дерево з $$$n$$$ вершин з коренем у вершині $$$1$$$, де на кожній вершині записано число. На $$$i$$$-й вершині записано число $$$a_i$$$.
Нагадаємо, що деревом називається зв'язний граф без циклів. Кореневим деревом називається дерево, в якому вибрана одна вершина — корінь.
Предком вершини $$$v$$$ в кореневому дереві називають усі вершини, які лежать на шляху від $$$v$$$ до кореня крім самої вершини $$$v$$$. Піддеревом вершини $$$v$$$ називають множину всіх вершин, для яких $$$v$$$ є предком і саму вершину $$$v$$$.
XOR сумою множини $$$S = (u_1, u_2, u_3, \dots, u_k)$$$ називається число $$$u_1 \oplus u_2 \oplus u_3 \oplus \dots \oplus u_k$$$, де $$$\oplus$$$ — операція побітової виключної диз'юнкції, яка позначається як «xor» в мові Pascal і «^» в мовах C++/Java/Python.
Для множини чисел $$$S$$$ розглянемо множину XOR-сум усіх можливих підмножин $$$S$$$. Назвемо цю множину $$$F(S)$$$.
Друг Ксоні постійно питає в неї питання — "Якщо розглянути множину всіх чисел, записаних в піддереві вершини $$$v$$$ (назвемо її $$$U_v$$$), то яке число в множині $$$F(U_v)$$$ буде $$$k$$$-е за зростанням?". Тобто, якщо взяти всі числа з піддерева вершини $$$v$$$, розглянути всі XOR-суми їх підмножин, то яке число в отриманій множині буде на $$$k$$$-му місці за зростанням? Якщо такого числа немає ($$$k > |F(U_v)|$$$), то Ксоня відповідає числом $$$-1$$$. Зверніть увагу, що $$$F(U_v)$$$ — множина, а не мультимножина. Тобто, якщо одне число зустрічається кілька разів, то його потрібно враховувати лише один раз.
Також, іноді друг Ксоні просить її змінити одне з чисел в дереві.
Перший рядок містить два цілі числа $$$n, g$$$ ($$$2 \leq n \leq 5 \cdot 10^4$$$, $$$0 \leq g \leq 7$$$) — кількість вершин в дереві та номер групи.
Кожен з наступних $$$n - 1$$$ рядків містить по два цілі числа $$$x_i, y_i$$$ ($$$ 1 \leq x_i, y_i \leq n$$$). Це означає, що в дереві проведено ребро між вершинами $$$x_i$$$ і $$$y_i$$$. Гарантується, що граф — дерево.
Наступний рядок містить $$$n$$$ цілих чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i < 2^{20}$$$) — масив $$$a$$$ початкових чисел на вершинах дерева.
Наступний рядок містить одне ціле число $$$q$$$ ($$$1 \leq q \leq 5 \cdot 10^4$$$) — кількість запитів.
Кожен з наступних $$$q$$$ рядків описує один запит.
Запити на зміну числа в дереві мають вигляд $$$1 \ x_i \ y_i$$$ ($$$1 \leq x_i \leq n$$$, $$$ 0 \leq y_i < 2^{20}$$$). Такий запит означає, що тепер на $$$x_i$$$-й вершині записано число $$$y_i$$$.
Запити іншого типу мають вигляд $$$2 \ v_i \ k_i$$$ ($$$1 \leq v_i \leq n$$$, $$$1 \leq k_i \leq 10^9$$$). Такий запит означає, що потрібно знайти $$$k_i$$$-те за зростанням число у множині $$$F(U_{v_i})$$$, де $$$U_{v_i}$$$ — множина чисел в піддереві вершини $$$v_i$$$, а $$$F(U_{v_i})$$$ — множина усіх можливих XOR-сум її підмножин. Якщо $$$k_i > |F(U_{v_i})|$$$, виведіть $$$-1$$$.
На кожний запит другого типу виведіть відповідь в окремому рядку.
5 0 1 2 1 5 2 3 2 4 4 2 3 1 2 7 2 2 4 2 1 2 2 2 3 1 3 4 2 5 1 2 2 8 2 1 5
3 1 2 0 7 4
Пояснення першого прикладу. Числа біля вершин — $$$a_i$$$.
$$$F([1,2,3]) = [0, 1, 2, 3]$$$.
В другому запиті розглядається все піддерево. $$$F([1, 2, 3, 4]) = [0,1,2,3,4,5,6,7]$$$.
Після зміни одного числа дерево має такий вигляд.
Тепер в піддереві вершини $$$2$$$ числа $$$1, 2, 4$$$.
$$$F([1,2,4]) = [0,1,2,3,4,5,6,7]$$$.