Земля коров
Земля Коров - это специальный парк развлечений для коров, где они гуляют, едят вкусную траву и посещают различные коровьи аттракционы (особенно популярны каталки).
Всего имеется n различных аттракционов. Определенные пары аттракционов соединены дорожками, всего их n − 1, при этом всегда существует единственный путь между любыми двумя достопримечательностями. У каждого аттракциона i есть целочисленное значение удовольствия e[i], которое может меняться в течение дня, так как одни аттракционы более привлекательны утром, а другие - во второй половине дня.
Корова, которая путешествует от аттракциона i к аттракциону j, может испытать удовольствие от всех аттракционов на пути от i до j. Любопытно, что общее значение удовольствия от всего этого маршрута определяется поразрядным XOR всех значений удовольствия вдоль маршрута, включая аттракционы i и j.
Помогите коровам определить значения удовольствий от маршрутов, которые они планируют использовать во время своей следующей поездки в Землю Коров.
Входные данные
Первая строка содержит число n (2 ≤ n ≤ 10^5) и количество запросов q (1 ≤ q ≤ 10^5). Следующая строка содержит e[1]...e[n] (0 ≤ e[i] ≤ 10^9). Каждая из следующих n - 1 строк описывает путь в виде двух целочисленных номеров аттракционов a и b (оба находятся в диапазоне 1 ... n). Наконец, каждая из последних q строк описывает либо обновление одного из значений e[i], либо запрос на получение удовольствия от маршрута. Строка формы "1 i v" указывает, что e[i] следует обновить до значения v, а строка формы "2 i j" - это запрос на значение удовольствия от маршрута, соединяющего достопримечательности i и j.
Выходные данные
Для каждого запроса вида "2 i j" выведите в отдельной строке значение удовольствия от маршрута от i до j.