Земля корів#10347
Земля Коров — це особливий парк розваг для корів, де вони можуть гуляти, ласувати смачною травою та відвідувати різноманітні коров'ячі атракціони (особливо популярні каталки).
У парку є різних атракціонів. Деякі пари атракціонів з'єднані доріжками, всього їх n - 1, що забезпечує існування єдиного шляху між будь-якими двома атракціонами. Кожен атракціон має ціле значення задоволення e_i, яке може змінюватися протягом дня, оскільки одні атракціони привабливіші вранці, а інші — у другій половині дня.
Корова, яка подорожує від атракціону до атракціону , може отримати задоволення від усіх атракціонів на шляху від до . Загальне значення задоволення від цього маршруту визначається побітовим XOR всіх значень задоволення вздовж маршруту, включаючи атракціони та .
Допоможіть коровам визначити значення задоволень від маршрутів, які вони планують використовувати під час своєї наступної поїздки в Землю Коров.
Перший рядок містить число (2 \le n \le 10^5) та кількість запитів (1 \le q \le 10^5). Наступний рядок містить e_1, \ldots, e_n (0 \le e_i \le 10^9). Кожен з наступних n - 1 рядків описує шлях у вигляді двох цілих номерів атракціонів та (обидва знаходяться в діапазоні 1, \ldots, n). Нарешті, кожен з останніх рядків описує або оновлення одного з значень e_i, або запит на отримання задоволення від маршруту. Рядок форми "1 i v" вказує, що e_i слід оновити до значення , а рядок форми "2 i j" — це запит на значення задоволення від маршруту, що з'єднує атракціони та .
Для кожного запиту виду "2 i j" виведіть в окремому рядку значення задоволення від маршруту від до .
Приклад 1