Cow Land est un parc d'attractions spécial pour les vaches : elles se promènent, mangent de l'herbe délicieuse et visitent diverses attractions (les montagnes russes bovines sont particulièrement populaires).

Il y a $N$ attractions différentes ($2 \leq N \leq 10^5$). Certaines paires sont reliées par des chemins, $N-1$ au total, de sorte qu'un unique itinéraire existe entre deux attractions quelconques. Chaque attraction $i$ a une valeur entière de plaisir $e_i$, qui peut changer dans la journée : certaines plaisent davantage le matin, d'autres en fin d'après-midi.

Une vache allant de $i$ à $j$ profite de toutes les attractions sur l'itinéraire de $i$ à $j$. Curieusement, le plaisir total est le XOR bit à bit de toutes les valeurs sur l'itinéraire, y compris celles de $i$ et $j$.

Aidez les vaches à déterminer le plaisir des itinéraires prévus lors de leur prochaine visite à Cow Land.

Entrée

La première ligne contient $N$ et le nombre de requêtes $Q$ ($1 \leq Q \leq 10^5$). La suivante contient $e_1 \ldots e_N$ ($0 \leq e_i \leq 10^9$). Les $N-1$ lignes suivantes décrivent chacune un chemin par deux identifiants entiers $a$ et $b$ (dans $1 \ldots N$). Les $Q$ dernières décrivent une modification de $e_i$ ou une requête de plaisir d'itinéraire. « 1 $i$ $v$ » met $e_i$ à $v$ ; « 2 $i$ $j$ » demande le plaisir entre $i$ et $j$.

Dans des tests valant au plus 50% des points, les valeurs des attractions ne changent pas.

Sortie

Pour chaque requête « 2 $i$ $j$ », affichez sur une ligne le plaisir de l'itinéraire de $i$ à $j$.

Exemples

Entrée 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

Sortie 1

21
20
4
20

Auteur du problème : Charles Bailey