Cow Land to specjalny park rozrywki dla krów: spacerują, jedzą pyszną trawę i odwiedzają różne atrakcje (krowia kolejka górska jest szczególnie popularna).

Jest $N$ różnych atrakcji ($2 \leq N \leq 10^5$). Niektóre pary łączą ścieżki, w sumie $N-1$, tak że między dowolnymi dwiema atrakcjami istnieje dokładnie jedna trasa po ścieżkach. Każda atrakcja $i$ ma całkowitą wartość przyjemności $e_i$, zmienną w ciągu dnia: niektóre są ciekawsze rano, inne późnym popołudniem.

Krowa idąca z $i$ do $j$ doświadcza wszystkich atrakcji na trasie z $i$ do $j$. Co ciekawe, całkowita przyjemność to bitowy XOR wszystkich wartości na trasie, włącznie z $i$ i $j$.

Pomóż krowom określić przyjemność tras planowanych na następną wizytę w Cow Land.

Wejście

Pierwszy wiersz zawiera $N$ i liczbę zapytań $Q$ ($1 \leq Q \leq 10^5$). Następny zawiera $e_1 \ldots e_N$ ($0 \leq e_i \leq 10^9$). Kolejne $N-1$ wierszy opisują ścieżki dwiema całkowitymi identyfikacjami $a$ i $b$ (obie w $1 \ldots N$). Ostatnie $Q$ wierszy opisują aktualizację $e_i$ lub zapytanie o trasę. „1 $i$ $v$” zmienia $e_i$ na $v$; „2 $i$ $j$” pyta o przyjemność między $i$ i $j$.

W testach wartych najwyżej 50% punktów wartości atrakcji się nie zmieniają.

Wyjście

Dla każdego zapytania „2 $i$ $j$” wypisz w jednym wierszu przyjemność trasy z $i$ do $j$.

Przykład

Wejście 1

5 5
1 2 4 8 16
1 2
1 3
3 4
3 5
2 1 5
1 1 16
2 3 5
2 1 5
2 1 3

Wyjście 1

21
20
4
20

Autor zadania: Charles Bailey