В квантовом протоколе верификации цифровых ключей зафиксирована последовательность состояний кубитов, закодированная массивом неотрицательных целых чисел a_1, a_2, ..., a_n.

Для проверки целостности протокола требуется обработать q запросов. В каждом запросе заданы границы окна l и r (1 <= l <= r <= n). Для этого окна необходимо вычислить итоговый контрольный ключ — побитовый XOR всех значений на отрезке от l до r включительно:

a_l XOR a_{l+1} XOR ... XOR a_r

Для каждого запроса выведите полученное значение.

Входные данные

Первая строка содержит два целых числа n и q — длину последовательности кубитов и количество запросов.

Вторая строка содержит n целых чисел a_i — значения, соответствующие состояниям кубитов.

Каждая из следующих q строк содержит два целых числа l и r — границы окна, для которого нужно вычислить XOR.

Выходные данные

Для каждого запроса выведите в отдельной строке одно целое число — XOR всех элементов на отрезке [l, r].

Ограничения

• 1 <= n, q <= 2 * 10^5
• 0 <= a_i <= 10^9
• 1 <= l <= r <= n

Примеры

Пример 1

Входные данные

5 6
0 1 2 3 4
1 1
1 5
2 3
5 5
4 5
2 5

Выходные данные

0
4
3
4
7
4

Пример 2

Входные данные

6 7
0 1000000000 0 1000000000 0 1000000000
1 6
1 1
6 6
2 2
1 2
5 6
2 6

Выходные данные

1000000000
0
1000000000
1000000000
1000000000
1000000000
1000000000