Із XOR з любов'ю#11546

Із XOR з любов'ю

2 секунди

128 мегабайтів

Дуже складна

Знову XOR, знову запити, знову дерево — романтика (с) Ануар Серіков

Де XOR немає місця словам. Отже, давайте рухатися далі до задачі.

У вас є кореневе дерево з $n$ вершинами, пронумерованими від $1$ до $n$ . Кожна вершина має певне значення. Вершина $1$ є коренем дерева.

Вам потрібно обробити $q$ запитів двох типів:

$1 v x$ — замініть значення у всіх вершинах піддерева вершини $v$ . Якщо у вершині записано число $y$ , замініть його на $x \oplus y$ x \oplus y.
$2 u v$ — знайдіть мінімальне значення серед чисел на простому шляху з вершини $u$ до вершини $v$ . Тобто, якщо числа на цьому шляху — це $a_{1}, a_{2}, \dots, a_{k}$ a_1, a_2, \dots, a_k, то відповіддю буде мінімум цієї послідовності.

Вхідні дані

Перший рядок містить два цілі числа $n (1 \leq n \leq 3 * 1 0^{4})$ n~(1 \le n \le 3*10^4) — кількість вершин у дереві, і $q$ $(1 \leq q \leq 3 * 1 0^{4})$ (1 \le q \le 3*10^4) — кількість запитів.

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

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

Останні $q$ рядків описують запити. Перше число в $i$ -му рядку $t y p e_{i}$ type_i — тип $i$ -го запиту. Якщо $t y p e_{i} = 1$ type_i = 1, то слідують два цілі числа $v_{i}$ v_i і $x_{i} (1 \leq v_{i} \leq n$ x_i~(1 \le v_i \le n, $0 \leq x_{i} < 2^{20})$ 0 \le x_i < 2^{20}), інакше слідують два цілі числа $u_{i}$ u_i і $v_{i} (1 \leq u_{i}, v_{i} \leq n)$ v_i~(1 \le u_i, v_i \le n). Всі вхідні числа є цілими.

Вихідні дані

Для кожного запиту 2-го типу виведіть в окремому рядку одне ціле число — відповідь на запит.

Приклади

$\oplus$ — виключаюче OR, наприклад $3 \oplus 5 = 6$ 3 \oplus 5 = 6.

Приклад 1