Земля корів
Земля Коров — це особливий парк розваг для корів, де вони можуть гуляти, ласувати смачною травою та відвідувати різноманітні коров'ячі атракціони (особливо популярні каталки).
У парку є n різних атракціонів. Деякі пари атракціонів з'єднані доріжками, всього їх n − 1, що забезпечує існування єдиного шляху між будь-якими двома атракціонами. Кожен атракціон i має ціле значення задоволення e[i], яке може змінюватися протягом дня, оскільки одні атракціони привабливіші вранці, а інші — у другій половині дня.
Корова, яка подорожує від атракціону i до атракціону j, може отримати задоволення від усіх атракціонів на шляху від i до j. Загальне значення задоволення від цього маршруту визначається побітовим XOR всіх значень задоволення вздовж маршруту, включаючи атракціони i та j.
Допоможіть коровам визначити значення задоволень від маршрутів, які вони планують використовувати під час своєї наступної поїздки в Землю Коров.
Вхідні дані
Перший рядок містить число n (2 ≤ n ≤ 10^5) та кількість запитів q (1 ≤ q ≤ 10^5). Наступний рядок містить e[1]...e[n] (0 ≤ e[i] ≤ 10^9). Кожен з наступних n - 1 рядків описує шлях у вигляді двох цілих номерів атракціонів a та b (обидва знаходяться в діапазоні 1 ... n). Нарешті, кожен з останніх q рядків описує або оновлення одного з значень e[i], або запит на отримання задоволення від маршруту. Рядок форми "1 i v" вказує, що e[i] слід оновити до значення v, а рядок форми "2 i j" - це запит на значення задоволення від маршруту, що з'єднує атракціони i та j.
Вихідні дані
Для кожного запиту виду "2 i j" виведіть в окремому рядку значення задоволення від маршруту від i до j.