Ксоня та дерево
ліміт часу на тест
5 seconds
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

У Ксоні є кореневе дерево з $$$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$$$.

Вихідні дані

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

Система оцінки

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

Приклад

Вхідні дані
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$$$.

В першому запиті розглядається піддерево вершини $$$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]$$$.