Ксоня та дерево

У Ксоні є кореневе дерево з $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 \cdots \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)$ — множина, а не мультимножина. Тобто, якщо одне число зустрічається кілька разів, то його потрібно враховувати лише один раз.

Також, іноді друг Ксоні просить її змінити одне з чисел в дереві.

Giriş verilənləri

Перший рядок містить два цілі числа $n,g$ ($2\le n\le 5\cdot 10^4$, $0\le g\le 7$) — кількість вершин в дереві та номер групи.

Кожен з наступних $n-1$ рядків містить по два цілі числа $x_i,y_i$ ($1\le x_i,y_i\le n$). Це означає, що в дереві проведено ребро між вершинами $x_i$ і $y_i$. Гарантується, що граф — дерево.

Наступний рядок містить $n$ цілих чисел $a_1,a_2,\dots ,a_n$ ($0\le a_i<2^{20}$) — масив $a$ початкових чисел на вершинах дерева.

Наступний рядок містить одне ціле число $q$ ($1\le q\le 5\cdot 10^4$) — кількість запитів.

Кожен з наступних $q$ рядків описує один запит.

Запити на зміну числа в дереві мають вигляд $1x_i{y}_i$ ($1\le x_i\le n$, $0\le y_i<2^{20}$). Такий запит означає, що тепер на $x_i$-й вершині записано число $y_i$.

Запити іншого типу мають вигляд $2v_i{k}_i$ ($1\le v_i\le n$, $1\le k_i\le 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$.

Çıxış verilənləri

На кожний запит другого типу виведіть відповідь в окремому рядку.

Nümunələr

Qeyd

Пояснення першого прикладу. Числа біля вершин — $a_i$.

В першому запиті розглядається піддерево вершини $2$. Воно містить числа $1,2,3$.

$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]$.

Qiymətləndirmə

1. ($6$ балів): $q,n\le 15$.

2. ($16$ балів): $q,n\le 500$.

3. ($18$ балів): $q,n\le 2000$.

4. ($7$ балів): У всіх запитах другого типу $v_i=1$.

5. ($13$ балів): Немає запитів на зміну числа.

6. ($11$ балів): Всі $a_i,y_i$ — степені числа 2.

7. ($29$ балів): Без додаткових обмежень.