Cow Land ist ein besonderer Vergnügungspark für Kühe: Sie spazieren, fressen leckeres Gras und besuchen verschiedene Attraktionen (die Kuh-Achterbahn ist besonders beliebt).

Es gibt $N$ verschiedene Attraktionen ($2 \leq N \leq 10^5$). Manche Paare sind durch Wege verbunden, insgesamt $N-1$, sodass zwischen je zwei Attraktionen genau eine Route aus diesen Wegen existiert. Jede Attraktion $i$ hat einen ganzzahligen Spaßwert $e_i$, der sich tagsüber ändern kann: Manche sind morgens reizvoller, andere am späten Nachmittag.

Eine Kuh auf dem Weg von $i$ nach $j$ erlebt alle Attraktionen auf der Route von $i$ nach $j$. Seltsamerweise ist der gesamte Spaßwert das bitweise XOR aller Werte entlang der Route, einschließlich $i$ und $j$.

Hilf den Kühen, die Spaßwerte ihrer geplanten Routen beim nächsten Besuch in Cow Land zu bestimmen.

Eingabe

Die erste Zeile enthält $N$ und die Anfragezahl $Q$ ($1 \leq Q \leq 10^5$). Die nächste enthält $e_1 \ldots e_N$ ($0 \leq e_i \leq 10^9$). Die nächsten $N-1$ Zeilen beschreiben Wege durch zwei ganzzahlige IDs $a$ und $b$ (beide im Bereich $1 \ldots N$). Die letzten $Q$ Zeilen beschreiben eine Änderung von $e_i$ oder eine Routenanfrage. „1 $i$ $v$“ setzt $e_i$ auf $v$; „2 $i$ $j$“ fragt den Spaßwert zwischen $i$ und $j$ ab.

In Testdaten für höchstens 50% der Punkte ändern sich die Attraktionswerte nicht.

Ausgabe

Gib für jede Anfrage „2 $i$ $j$“ den Spaßwert der Route von $i$ nach $j$ in einer Zeile aus.

Beispiele

Eingabe 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

Ausgabe 1

21
20
4
20

Aufgabenautor: Charles Bailey