İnək torpağı

Kənd Kərgədanları - kərgədanlar üçün xüsusi bir əyləncə parkıdır. Burada kərgədanlar gəzir, dadlı ot yeyir və müxtəlif attraksionlara, xüsusilə də sürüşkənlərə baş çəkirlər.

Parkda ümumilikdə n müxtəlif attraksion mövcuddur. Bəzi cüt attraksionlar yollarla birləşdirilib və ümumilikdə n − 1 yol var, belə ki, hər hansı iki attraksion arasında həmişə tək bir yol mövcuddur. Hər bir attraksionun i tam ədədi ilə ifadə olunan zövq dəyəri e[i] var. Bu dəyərlər gün ərzində dəyişə bilər, çünki bəzi attraksionlar səhər daha cəlbedici, digərləri isə günün ikinci yarısında daha cəlbedici olur.

Attraksion i-dən j-yə səyahət edən kərgədan, i-dən j-yə qədər olan yolda bütün attraksionlardan zövq ala bilər. Bu marşrutun ümumi zövq dəyəri, marşrut boyunca olan bütün zövq dəyərlərinin, o cümlədən i və j attraksionlarının, bitwise XOR-u ilə müəyyən edilir.

Kərgədanlara Kənd Kərgədanlarına növbəti səfərləri zamanı istifadə etməyi planlaşdırdıqları marşrutların zövq dəyərlərini müəyyən etməyə kömək edin.

Giriş Məlumatları

Birinci sətir n (2 ≤ n ≤ 10^5) və sorğuların sayı q (1 ≤ q ≤ 10^5) ədədini ehtiva edir. Növbəti sətir e[1]...e[n] (0 ≤ e[i] ≤ 10^9) dəyərlərini ehtiva edir. Sonrakı n - 1 sətirin hər biri iki tam ədəd a və b şəklində bir yolu təsvir edir (hər ikisi 1 ... n aralığında). Nəhayət, son q sətirin hər biri ya e[i] dəyərlərindən birinin yenilənməsini, ya da marşrutun zövq dəyərinin sorğusunu təsvir edir. "1 i v" formasında olan sətir e[i]-nin v dəyərinə yenilənməli olduğunu göstərir, "2 i j" formasında olan sətir isə i və j görməli yerlərini birləşdirən marşrutun zövq dəyərinin sorğusudur.

Çıxış Məlumatları

Hər bir "2 i j" sorğusu üçün i-dən j-yə qədər olan marşrutun zövq dəyərini ayrıca sətirdə çıxarın.