Maraqlı

Ledi maraqlı bir problem hazırlayıb.

n elementdən ibarət a massiviniz var.

Bu massivdə bəzi cüt elementlərin yerlərini dəyişməyə icazə verilir, lakin hər bir elementin mövqeyi yalnız bir dəfə dəyişdirilə bilər. Bu dəyişikliklər nəticəsində b massivi əldə ediləcək.

n ölçülü c massivini belə təyin edək: c[i] = min(a[i], b[i]).

Bu problemin cavabı c[1] ⊕ c[2] ⊕ ... ⊕ c[n] ifadəsinin minimal mümkün dəyəridir.

Ledi m altmassivə malikdir və hər biri üçün cavabı tapmaq istəyir. Xahiş edirik, ona bu işdə kömək edin!

Qeyd edək ki, bu m məsələnin hər biri müstəqil şəkildə həll edilməlidir.

Giriş formatı

Birinci sətir n və m tam ədədlərini (1 ≤ n, m ≤ 150 000) — elementlərin sayı və məsələlərin sayını ehtiva edir.

İkinci sətir n tam ədəd a[1], a[2], ..., a[n] (0 ≤ a[i] < 2^30) — elementləri ehtiva edir.

Sonrakı m sətirin hər biri iki tam ədəd l və r (1 ≤ l ≤ r ≤ n) ehtiva edir ki, bu da altmassiv [a[l], a[l+1], ..., a[r]] üçün problemi həll etməli olduğunuzu bildirir.

Çıxış formatı

m tam ədəd çıxarın — məsələlərin cavabları.

Qeyd

Birinci məsələdə altmassivin elementlərini yer dəyişdirmək mümkün deyil.

İkinci məsələdə optimal nəticə əldə etmək üçün altmassivin elementlərini yer dəyişdirmək lazım deyil.

Üçüncü məsələdə optimal nəticə əldə etmək üçün 5 və 6 elementlərini yer dəyişdirmək lazımdır.

Dördüncü məsələdə mümkün həllərdən biri belədir: aşağıdakı cütləri yer dəyişdirmək lazımdır (1, 3), (2, 6) və (4, 5).

x ⊕ y ifadəsi x və y ədədlərinə bitwise XOR əməliyyatını tətbiq etməyi bildirir. Bu əməliyyat bütün müasir proqramlaşdırma dillərində mövcuddur, məsələn, C++ və Java dillərində «ˆ» kimi, Pascalda isə «xor» kimi göstərilir.