CowLand это специальный парк развлечений для коров, где они бродят, едят
вкусную траву и посещают различные аттракционы для коров.
Всего имеется \(N\) различных аттракционов (\(2 \leq N \leq 10^5\)).
Определённые пары аттракционов связаны дорожками, которых всего \(N-1\) штук,
таким образом, что существует единственный путь, состоящий из различных дорожек
между любыми двумя аттракционами. Каждый аттракцион \(i\) имеет целую величину
удовольствия \(e_i\), которая может измениться в течение дня, поскольку некоторые
аттракционы более привлекательны утром, а некоторые - вечером.
Корова, которая проходит от аттракциона \(i\) до аттракциона \(j\) получает
удовольствие всех аттракционов маршрута от \(i\) до \(j\). Забавно, что общее удовольствие
от всего маршрута вычисляется как побитовое XOR всех удовольствий в течение
маршрута, включая удовольствия в аттракционах \(i\) и \(j\).
Помогите коровам определить величины удовольствий маршрутов, которые
коровы собираются пройти в CowLand.
ФОРМАТ ВВОДА (файл cowland.in):
Первая строка ввода содержит
\(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\) (
\(e_i\) should be updated to value
\(v\)).
Строка вида "2
\(i\) \(j\)" это запрос на удовольствие от маршрута, соединяющего
аттракционы
\(i\) и
\(j\).
В тестах не более 50% не будет изменений удовольствий на аттракционах.
ФОРМАТ ВЫВОДА (файл cowland.out):
Для каждого запроса вида "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
|
21
20
4
20
|