Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

D. Ксюша и битовые операции
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У начинающего программиста Ксюши есть последовательность a, состоящая из 2n неотрицательных целых чисел: a1, a2, ..., a2n. Сейчас Ксюша изучает битовые операции. Чтобы лучше понять как они работают, Ксюша решила подсчитать некоторое значение v по a.

А именно, значение v считается в несколько итераций. На первой итерации, Ксюша записывает новую последовательность a1 or a2, a3 or a4, ..., a2n - 1 or a2n, состоящую из 2n - 1 элементов. Другими словами, она записывает побитовое ИЛИ соседних элементов последовательности a. На второй итерации, Ксюша записывает побитовое исключающее ИЛИ соседних элементов полученной после первой итерации последовательности. На третьей итерации Ксюша записывает побитовое ИЛИ соседних элементов последовательности, полученной после второй итерации. И так далее операции побитовое исключающее ИЛИ и побитовое ИЛИ чередуются. В конце концов получится последовательность, состоящая из одного элемента, этот элемент и равен v.

Рассмотрим пример, пусть последовательность a = (1, 2, 3, 4). Тогда запишем все преобразования (1, 2, 3, 4)  →  (1 or 2 = 3, 3 or 4 = 7)  →  (3 xor 7 = 4), в итоге v = 4.

Вам задана изначальная последовательность Ксюши. Но посчитать значение v по заданной последовательности было бы слишком просто, поэтому Вам дополнительно заданы m запросов. Каждый запрос — это пара целых чисел p, b. Запрос p, b означает, что нужно выполнить присвоение ap = b. После каждого запроса, нужно вывести новое значение v посчитанное по новой последовательности a.

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

В первой строке записаны два целых числа n и m (1 ≤ n ≤ 17, 1 ≤ m ≤ 105). В следующей строке записаны 2n целых чисел a1, a2, ..., a2n (0 ≤ ai < 230). В каждой из следующих m строк записаны запросы. В i-ой строке записаны целые числа pi, bi (1 ≤ pi ≤ 2n, 0 ≤ bi < 230)i-ый запрос.

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

Выведите m целых чисел — i-ое число обозначает значение v посчитанное для последовательности a после выполнения i-ого запроса.

Примеры
Входные данные
2 4
1 6 3 5
1 4
3 4
1 2
1 2
Выходные данные
1
3
3
3
Примечание

Для справок по битовым операциям вы можете использовать информацию по ссылке: http://ru.wikipedia.org/wiki/Битовые_операции