Земля Коров - это специальный парк развлечений для коров, где они гуляют, едят вкусную траву и посещают различные коровьи аттракционы (особенно популярны каталки).

Всего имеется 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.