Cow Land es un parque de atracciones especial para vacas: pasean, comen hierba deliciosa y visitan diversas atracciones (la montaña rusa bovina es especialmente popular).

Hay $N$ atracciones distintas ($2 \leq N \leq 10^5$). Algunas parejas se conectan por caminos, $N-1$ en total, de modo que hay una ruta única entre cualquier pareja. Cada atracción $i$ tiene un disfrute entero $e_i$, que puede cambiar durante el día: algunas atraen más por la mañana y otras al final de la tarde.

Una vaca que viaja de $i$ a $j$ experimenta todas las atracciones de la ruta de $i$ a $j$. Curiosamente, el disfrute total es el XOR bit a bit de todos los valores de la ruta, incluidos $i$ y $j$.

Ayuda a las vacas a determinar el disfrute de las rutas que usarán en su próxima visita a Cow Land.

Entrada

La primera línea contiene $N$ y la cantidad de consultas $Q$ ($1 \leq Q \leq 10^5$). La siguiente contiene $e_1 \ldots e_N$ ($0 \leq e_i \leq 10^9$). Las siguientes $N-1$ líneas describen caminos mediante dos identificadores enteros $a$ y $b$ (ambos en $1 \ldots N$). Las últimas $Q$ líneas describen una actualización de $e_i$ o una consulta de disfrute. «1 $i$ $v$» actualiza $e_i$ a $v$; «2 $i$ $j$» consulta la ruta entre $i$ y $j$.

En pruebas que valen como máximo el 50% de los puntos, los valores de las atracciones no cambian.

Salida

Para cada consulta «2 $i$ $j$», imprime en una línea el disfrute de la ruta de $i$ a $j$.

Ejemplos

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

Salida 1

21
20
4
20

Autor del problema: Charles Bailey