Земля коров
Земля коров
Земля Коров - это специальный парк развлечений для коров, где они гуляют, едят вкусную траву и посещают различные коровьи аттракционы (особенно популярны каталки).
Всего имеется n различных аттракционов. Определенные пары аттракционов соединены дорожками, всего их n − 1, при этом всегда существует единственный путь между любыми двумя достопримечательностями. У каждого аттракциона i есть целочисленное значение удовольствия ei
, которое может меняться в течение дня, так как одни аттракционы более привлекательны утром, а другие - во второй половине дня.
Корова, которая путешествует от аттракциона i к аттракциону j, может испытать удовольствие от всех аттракционов на пути от i до j. Любопытно, что общее значение удовольствия от всего этого маршрута определяется поразрядным XOR всех значений удовольствия вдоль маршрута, включая аттракционы i и j.
Помогите коровам определить значения удовольствий от маршрутов, которые они планируют использовать во время своей следующей поездки в Землю Коров.
Входные данные
Первая строка содержит число n (2 ≤ n ≤ 105
) и количество запросов q (1 ≤ q ≤ 105
). Следующая строка содержит e1
...en
(0 ≤ ei
≤ 109
). Каждая из следующих n - 1 строк описывает путь в виде двух целочисленных номеров аттракционов a и b (оба находятся в диапазоне 1 ... n). Наконец, каждая из последних q строк описывает либо обновление одного из значений ei
, либо запрос на получение удовольствия от маршрута. Строка формы "1 i v" указывает, что ei
следует обновить до значения v, а строка формы "2 i j" - это запрос на значение удовольствия от маршрута, соединяющего достопримечательности i и j.
Выходные данные
Для каждого запроса вида "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