Cow Land è un parco divertimenti speciale per mucche: passeggiano, mangiano erba deliziosa e visitano varie attrazioni (le montagne russe bovine sono particolarmente popolari).

Ci sono $N$ attrazioni diverse ($2 \leq N \leq 10^5$). Alcune coppie sono collegate da sentieri, $N-1$ in totale, così che esiste un unico percorso fra due attrazioni qualsiasi. Ogni attrazione $i$ ha un divertimento intero $e_i$, che può cambiare durante il giorno: alcune sono più attraenti al mattino, altre nel tardo pomeriggio.

Una mucca che va da $i$ a $j$ prova tutte le attrazioni sul percorso da $i$ a $j$. Curiosamente, il divertimento totale è lo XOR bit a bit di tutti i valori lungo il percorso, compresi $i$ e $j$.

Aiuta le mucche a determinare il divertimento dei percorsi previsti per la prossima visita a Cow Land.

Input

La prima riga contiene $N$ e il numero di interrogazioni $Q$ ($1 \leq Q \leq 10^5$). La successiva contiene $e_1 \ldots e_N$ ($0 \leq e_i \leq 10^9$). Le successive $N-1$ righe descrivono sentieri con due identificatori interi $a$ e $b$ (entrambi in $1 \ldots N$). Le ultime $Q$ righe descrivono una modifica di $e_i$ o un'interrogazione sul divertimento. «1 $i$ $v$» aggiorna $e_i$ a $v$; «2 $i$ $j$» interroga il percorso fra $i$ e $j$.

Nei test che valgono al massimo il 50% dei punti, i valori delle attrazioni non cambiano.

Output

Per ogni interrogazione «2 $i$ $j$», stampa su una riga il divertimento del percorso da $i$ a $j$.

Esempi

Input 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

Output 1

21
20
4
20

Autore del problema: Charles Bailey