本题使用标准输入、标准输出，无需读写题面中提到的文件。

题目描述

牛之国（Cow Land）是一个专为奶牛打造的特殊游乐园，奶牛们在这里四处漫步、吃美味的草，并参观各种不同的奶牛景点（其中“过山牛车”尤其受欢迎）。 这里一共有 $N$ 个不同的景点（$2 \leq N \leq 10^5$）。一些景点对之间由小路连接，总共有 $N-1$ 条，并且这些连接方式保证任意两个景点之间都存在一条由若干小路组成的唯一路径。每个景点 $i$ 都有一个整数的愉悦值 $e_i$；由于有些景点早上更有吸引力，而有些景点下午更受欢迎，这个值会在一天中发生变化。 一头奶牛从景点 $i$ 前往景点 $j$ 时，会体验从 $i$ 到 $j$ 的路径上所有景点。有趣的是，这条完整路径的总愉悦值定义为该路径上所有景点愉悦值（包括景点 $i$ 和 $j$）的按位异或（XOR）。 请帮助奶牛们确定她们下一次前往牛之国时计划使用的路线的愉悦值。

输入格式

输入第一行包含 $N$ 和查询次数 $Q$（$1 \leq Q \leq 10^5$）。第二行包含 $e_1 \ldots e_N$（$0 \leq e_i \leq 10^9$）。接下来的 $N-1$ 行每行描述一条小路，给出两个景点编号 $a$ 和 $b$（均在范围 $1 \ldots N$）。 最后的 $Q$ 行每行描述一次对某个 $e_i$ 的更新或一次对路线愉悦值的查询。形如 "1 $i$ $v$" 的一行表示将 $e_i$ 更新为 $v$；形如 "2 $i$ $j$" 的一行表示查询连接景点 $i$ 与 $j$ 的路径的愉悦值。 在最多占总分 50% 的测试数据中，景点的值不会发生变化。

输出格式

对于每个形如 "2 $i$ $j$" 的查询，输出一行，表示从 $i$ 到 $j$ 的路径的愉悦值。

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

21
20
4
20

提示

题目作者：Charles Bailey

来源

USACO|2019|Gold