Cow Land — особый парк развлечений для коров: они гуляют, едят вкусную траву и посещают разные аттракционы (особенно популярны коровьи американские горки).

Всего есть $N$ различных аттракционов ($2 \leq N \leq 10^5$). Некоторые пары соединены дорожками, всего $N-1$, так что между любыми двумя существует единственный маршрут по дорожкам. У аттракциона $i$ целочисленное удовольствие $e_i$, которое может меняться за день: одни интереснее утром, другие — поздним днём.

Корова, идущая от $i$ к $j$, испытывает все аттракционы на маршруте от $i$ к $j$. Любопытно, что суммарное удовольствие маршрута равно побитовому XOR всех значений на нём, включая $i$ и $j$.

Помогите коровам определить удовольствие маршрутов, которыми они собираются воспользоваться при следующем посещении Cow Land.

Входные данные

Первая строка содержит $N$ и число запросов $Q$ ($1 \leq Q \leq 10^5$). Следующая содержит $e_1 \ldots e_N$ ($0 \leq e_i \leq 10^9$). Следующие $N-1$ строк описывают дорожки двумя целыми ID $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$.

Примеры

Входные данные 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

Выходные данные 1

21
20
4
20

Автор задачи: Charles Bailey