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

Обмеження на час виконання 5 секунд

Обмеження на використання пам'яті 256 мегабайтів

У Ксоні є кореневе дерево з $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 1 0^{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 1 0^{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 1 0^{9}$ ). Такий запит означає, що потрібно знайти $k_{i}$ -те за зростанням число у множині $F (U_{v_{i}})$ , де $U_{v_{i}}$ — множина чисел в піддереві вершини $v_{i}$ , а $F (U_{v_{i}})$ — множина усіх можливих XOR-сум її підмножин. Якщо $k_{i} > ∣ F (U_{v_{i}}) ∣$ , виведіть $- 1$ .

Вихідні дані

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

Приклади

Вхідні дані #1

Відповідь #1

Примітка

Пояснення першого прикладу. Числа біля вершин — $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]$ .

Оцінювання

( $6$ балів): $q, n \leq 15$ .
( $16$ балів): $q, n \leq 500$ .
( $18$ балів): $q, n \leq 2000$ .
( $7$ балів): У всіх запитах другого типу $v_{i} = 1$ .
( $13$ балів): Немає запитів на зміну числа.
( $11$ балів): Всі $a_{i}, y_{i}$ — степені числа 2.
( $29$ балів): Без додаткових обмежень.