Ледi вигадала задачу.

Задано масив a з n невiд’ємних чисел.

Дозволяється помiняти мiсцями деякi пари елементiв масиву, але мiняти позицiю кожного елементу дозволяється не бiльше одного разу. У результатi цих змiн буде отримано масив b.

Масив c розмiру n визначимо наступним чином: c[i] = min(ai, bi).

Вiдповiддю до такої задачi є мiнiмальне можливе значення c1 ⊕ c2 ⊕ . . . ⊕ cn.

У Ледi є m пiдмасивiв, на кожен з яких вона хоче знайти вiдповiдь. Допоможiть, будь ласка, їй це зробити!

Зауважте, що розв’язувати цi m задач потрiбно незалежно.

Формат вхiдних даних

Перший рядок мiстить два цiлi числа n та m (**1 ≤ n, m ≤ 150 000**) — кiлькiсть чисел та кiлькiсть задач.

Другий рядок мiстить n цiлих чисел a1, a2, . . . , an (**0 ≤ ai < 230**) — числа.

Кожен з наступних m рядкiв мiстить по два цiлi числа l та r (**1 ≤ l ≤ r ≤ n**), що означає, що Вам потрiбно рiшити задачу для пiдмасиву [**al , al+1, . . . , ar**].

Формат вихiдних даних

Вивед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».