Цікава#9096

Цікава

1 секунда

64 мегабайти

Дуже складна

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

Задано масив $a$ з $n$ невід'ємних чисел.

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

Масив $c$ розміру $n$ визначимо наступним чином: $c_{i} = min (a_{i}, b_{i})$ c_i = \min(a_i, b_i).

Відповіддю до такої задачі є мінімальне можливе значення $c_{1} \oplus c_{2} \oplus \dots \oplus c_{n}$ c_1 \oplus c_2 \oplus \ldots \oplus c_n.

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

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

Вхідні дані

Перший рядок містить два цілих числа $n$ та $m$ ( $1 \leq n, m \leq 150000$ 1 \leq n, m \leq 150\ 000) — кількість чисел та кількість задач.

Другий рядок містить $n$ цілих чисел $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n ( $0 \leq a_{i} < 2^{30}$ 0 \leq a_i < 2^{30}) — числа.

Кожен з наступних $m$ рядків містить по два цілі числа $l$ та $r$ ( $1 \leq l \leq r \leq n$ 1 \leq l \leq r \leq n), що означає, що Вам потрібно розв'язати задачу для підмасиву $a_{l}, a_{l + 1}, \dots, a_{r}$ a_l, a_{l+1}, \ldots, a_r.

Вихідні дані

Виведіть $m$ цілих чисел — відповіді на задачі.

Приклади

Приклад 1

Примітка

У першій задачі неможливо поміняти місцями елементи підмасиву.

У другій задачі для досягнення оптимального результату не потрібно поміняти місцями елементи підмасиву.

У третій задачі для досягнення оптимального результату потрібно поміняти місцями елементи $5$ та $6$ .

У четвертій задачі одним з можливих рішень є наступне: потрібно поміняти місцями наступні пари $(1, 3)$ , $(2, 6)$ та $(4, 5)$ .

Вираз $x \oplus y$ x \oplus y означає застосування побітової операції XOR до чисел $x$ і $y$ . Дана операція існує у всіх сучасних мовах програмування, наприклад, у мовах C++ і Java вона позначена як «^», а в Pascal як «xor».