XOR-dan məhəbbətlə#11546
Sən XOR, sənin sorğuların, sənin ağacın — romantika (c) Anuar Serikov
Burada XOR üçün sözlərə yer yoxdur. Beləliklə, gəlin məsələyə keçək.
Kökü zirvə olan zirvəli bir ağacımız var və bütün zirvələr -dən -ə qədər nömrələnib. Hər zirvədə bir ədəd yazılıb — bu, zirvənin dəyəridir.
Bu məsələdə siz sorğunu emal etməlisiniz. Sorğular iki növdə olur:
— zirvə -nin alt ağacında olan bütün ədədləri dəyişdirin. Yəni, əgər hansısa zirvədə ədədi yazılıbsa, onu x\oplus y ilə əvəzləmək lazımdır.
— zirvə -dan zirvə -yə qədər olan sadə yol üzərində yazılmış ədədlərin minimumunu tapın. Daha dəqiq desək: zirvə -dan zirvə -yə qədər olan yolda ədədlər a_1, a_2, ... , a_k olsun, bu sorğunun cavabı bu ardıcıllığın minimumu olacaq.
Birinci sətirdə iki tam ədəd n~(1 \le n \le 3*10^4) — ağacın zirvələrinin sayı və (1 \le q \le 3*10^4) — sorğuların sayı verilir.
İkinci sətirdə tam ədəddən ibarət ardıcıllıq a_1, a_2, \dots , a_n~(0 \le a_i < 2^{20}) — zirvələrdə yazılmış ədədlər verilir.
Sonra ağacın kənarlarını təsvir edən n - 1 sətir gəlir. Hər bir sətir iki tam ədəd x_i, y_i~(1 \leq x_i,y_i \leq n, x_i \ne y_i) — kənarla birləşdirilmiş zirvələr verilir. Qrafın əlaqəli ağac olduğu təmin edilir.
Son sətir sorğuları təsvir edir. -ci sətirdəki ilk ədəd type_i — -ci sorğunun növüdür. Əgər type_i = 1-dirsə, iki tam ədəd v_i və x_i~(1 \le v_i \le n, 0 \le x_i < 2^{20}) gəlir, əks halda iki tam ədəd u_i və v_i~(1 \le u_i, v_i \le n) gəlir. Bütün giriş ədədləri tam ədədlərdir.
Hər bir 2-ci növ sorğu üçün ayrı sətirdə bir tam ədəd — sorğunun cavabını çıxarın.
— istisna OR, məsələn 3\oplus 5 = 6.
Nümunə 1