Із XOR з любов'ю

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

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

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

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

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

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

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

Вхідні дані

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

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

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

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

Вихідні дані

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

Приклади

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

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

Відповідь #1

Відправки 14

Коефіцієнт прийняття 14%