Цiкава
Ледi вигадала задачу.
Задано масив a з n невiд’ємних чисел.
Дозволяється помiняти мiсцями деякi пари елементiв масиву, але мiняти позицiю кожного елементу дозволяється не бiльше одного разу. У результатi цих змiн буде отримано масив b.
Масив c розмiру n визначимо наступним чином: c[i] = min(a[i], b[i]).
Вiдповiддю до такої задачi є мiнiмальне можливе значення c[1] ⊕ c[2] ⊕ . . . ⊕ c[n].
У Ледi є m пiдмасивiв, на кожен з яких вона хоче знайти вiдповiдь. Допоможiть, будь ласка, їйце зробити!
Зауважте, що розв’язувати цi m задач потрiбно незалежно.
Вхідні дані
Перший рядок мiстить два цiлi числа n та m (1 ≤ n, m ≤ 150 000) — кiлькiсть чисел та кiлькiсть задач.
Другий рядок мiстить n цiлих чисел a[1], a[2], . . . , a[n] (0 ≤ a[i] < 2^30) — числа.
Кожен з наступних m рядкiв мiстить по два цiлi числа l та r (1 ≤ l ≤ r ≤ n), що означає, що Вам потрiбно рiшити задачу для пiдмасиву [a[l] , a[l+1], . . . , a[r]].
Вихідні дані
Виведiть m цiлих чисел — вiдповiдi на задачi.
####Примiтка
У першiй задачi неможливо помiняти мiсцями елементи пiдмасиву.
У друга задачi для досягнення оптимального результату не потрiбно помiняти мiсцями елементи пiдмасиву.
У третiй задачi для досягнення оптимального результату потрiбно помiняти мiсцями елементи 5 та 6.
У четвертiй задачi одним з можливих рiшень є наступне: потрiбно помiняти мiсцями наступнi пари (1, 3), (2, 6) та (4, 5).
Вираз x ⊕ y означає застосування побiтової операцiї XOR до чисел x i y. Дана операцiя iснує у всiх сучасних мовах програмування, наприклад, у мовах С++ i Java вона позначена як «ˆ», а в Pascal як «xor».