Cow Land é um parque de diversões especial para vacas: passeiam, comem relva deliciosa e visitam várias atrações (a montanha-russa bovina é particularmente popular).

Existem $N$ atrações diferentes ($2 \leq N \leq 10^5$). Certos pares são ligados por caminhos, $N-1$ no total, de modo que existe uma rota única entre quaisquer duas atrações. Cada atração $i$ tem um valor inteiro de diversão $e_i$, que pode mudar durante o dia: algumas são mais apelativas de manhã, outras ao fim da tarde.

Uma vaca que vai de $i$ a $j$ experimenta todas as atrações na rota de $i$ a $j$. Curiosamente, a diversão total é o XOR bit a bit de todos os valores na rota, incluindo os de $i$ e $j$.

Ajude as vacas a determinar a diversão das rotas planeadas para a próxima visita a Cow Land.

Entrada

A primeira linha contém $N$ e o número de consultas $Q$ ($1 \leq Q \leq 10^5$). A seguinte contém $e_1 \ldots e_N$ ($0 \leq e_i \leq 10^9$). As $N-1$ linhas seguintes descrevem caminhos por dois identificadores inteiros $a$ e $b$ (ambos em $1 \ldots N$). As últimas $Q$ linhas descrevem uma atualização de $e_i$ ou uma consulta de diversão. «1 $i$ $v$» atualiza $e_i$ para $v$; «2 $i$ $j$» consulta a rota entre $i$ e $j$.

Em testes que valem no máximo 50% dos pontos, os valores das atrações não mudam.

Saída

Para cada consulta «2 $i$ $j$», imprima numa linha a diversão da rota de $i$ a $j$.

Exemplos

Entrada 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

Saída 1

21
20
4
20

Autor do problema: Charles Bailey