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

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

5 секунд

256 мегабайтів

Середня

У Ксоні є кореневе дерево з $n$ вершин з коренем у вершині $1$ , де на кожній вершині записано число. На $i$ -й вершині записано число $a_{i}$ a_i.

Нагадаємо, що деревом називається зв'язний граф без циклів. Кореневим деревом називається дерево, в якому вибрана одна вершина — корінь.

Предком вершини $v$ в кореневому дереві називають усі вершини, які лежать на шляху від $v$ до кореня крім самої вершини $v$ . Піддеревом вершини $v$ називають множину всіх вершин, для яких $v$ є предком і саму вершину $v$ .

XOR сумою множини $S = (u_{1}, u_{2}, u_{3}, \dots, u_{k})$ S = (u_1, u_2, u_3, \dots, u_k) називається число $u_{1} \oplus u_{2} \oplus u_{3} \oplus \dots \oplus 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}$ U_v), то яке число в множині $F (U_{v})$ F(U_v) буде $k$ -е за зростанням?". Тобто, якщо взяти всі числа з піддерева вершини $v$ , розглянути всі XOR-суми їх підмножин, то яке число в отриманій множині буде на $k$ -му місці за зростанням? Якщо такого числа немає ( $k > ∣ F (U_{v}) ∣$ k > |F(U_v)|), то Ксоня відповідає числом $- 1$ . Зверніть увагу, що $F (U_{v})$ F(U_v) — множина, а не мультимножина. Тобто, якщо одне число зустрічається кілька разів, то його потрібно враховувати лише один раз.

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

Вхідні дані

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

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

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

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

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

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

Запити іншого типу мають вигляд $2 v_{i} k_{i}$ 2 \ v_i \ k_i ( $1 \leq v_{i} \leq n$ 1 \leq v_i \leq n, $1 \leq k_{i} \leq 1 0^{9}$ 1 \leq k_i \leq 10^9). Такий запит означає, що потрібно знайти $k_{i}$ k_i-те за зростанням число у множині $F (U_{v_{i}})$ F(U_{v_i}), де $U_{v_{i}}$ U_{v_i} — множина чисел в піддереві вершини $v_{i}$ v_i, а $F (U_{v_{i}})$ F(U_{v_i}) — множина усіх можливих XOR-сум її підмножин. Якщо $k_{i} > ∣ F (U_{v_{i}}) ∣$ k_i > |F(U_{v_i})|, виведіть $- 1$ .

Вихідні дані

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

Приклади

Приклад 1

Примітка

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

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

$F ([1, 2, 3]) = [0, 1, 2, 3]$ F([1,2,3]) = [0, 1, 2, 3].

В другому запиті розглядається все піддерево. $F ([1, 2, 3, 4]) = [0, 1, 2, 3, 4, 5, 6, 7]$ 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]$ F([1,2,4]) = [0,1,2,3,4,5,6,7].

Оцінювання

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