CF339D.Xenia and Bit Operations

Xenia the beginner programmer has a sequence a, consisting of 2_n_ non-negative integers: _a_1, _a_2, ..., a_2_n. Xenia is currently studying bit operations. To better understand how they work, Xenia decided to calculate some value v for a.

Namely, it takes several iterations to calculate value v. At the first iteration, Xenia writes a new sequence _a_1 or _a_2, _a_3 or a_4, ..., a_2_n - 1 or a_2_n, consisting of 2_n - 1 elements. In other words, she writes down the bit-wise OR of adjacent elements of sequence a. At the second iteration, Xenia writes the bitwise exclusive OR of adjacent elements of the sequence obtained after the first iteration. At the third iteration Xenia writes the bitwise OR of the adjacent elements of the sequence obtained after the second iteration. And so on; the operations of bitwise exclusive OR and bitwise OR alternate. In the end, she obtains a sequence consisting of one element, and that element is v.

Let's consider an example. Suppose that sequence a = (1, 2, 3, 4). Then let's write down all the transformations (1, 2, 3, 4)  →  (1 or 2 = 3, 3 or 4 = 7)  →  (3 xor 7 = 4). The result is v = 4.

You are given Xenia's initial sequence. But to calculate value v for a given sequence would be too easy, so you are given additional m queries. Each query is a pair of integers p, b. Query p, b means that you need to perform the assignment a__p = b. After each query, you need to print the new value v for the new sequence a.

初学者程序员 Xenia 有一个由 $2^n$ 个非负整数组成的序列 $a$：$a_1,\,a_2,\,\dots,\,a_{2n}$。Xenia 当前正在学习位运算。为了更好地理解其工作原理，Xenia 决定为序列 $a$ 计算某个值 $v$。

具体而言，计算值 $v$ 需要若干轮迭代。在第一轮迭代中，Xenia 写出一个新序列：$a_1\ \text{or}\ a_2,\,a_3\ \text{or}\ a_4,\,\dots,\,a_{2n-1}\ \text{or}\ a_{2n}$，该序列包含 $2^{n-1}$ 个元素；即，她将原序列 $a$ 中相邻元素进行按位或（bit-wise OR）运算。在第二轮迭代中，Xenia 对第一轮得到的序列中相邻元素进行按位异或（bit-wise XOR）运算。在第三轮迭代中，Xenia 对第二轮得到的序列中相邻元素再次进行按位或运算。依此类推；按位异或与按位或这两种运算交替进行。最终，她得到仅含一个元素的序列，该元素即为 $v$。

我们来看一个例子。假设序列 $a = (1,\,2,\,3,\,4)$。则所有变换过程如下：
$(1,\,2,\,3,\,4) \to (1\ \text{or}\ 2 = 3,\,3\ \text{or}\ 4 = 7) \to (3\ \text{xor}\ 7 = 4)$。结果为 $v = 4$。

你将获得 Xenia 的初始序列。但若仅对给定序列计算一次 $v$ 就显得过于简单了，因此你还会收到额外的 $m$ 个查询。每个查询是一对整数 $p,\,b$。查询 $(p,\,b)$ 表示执行赋值操作 $a_p = b$。每次查询后，你需要输出新序列 $a$ 对应的新值 $v$。

The first line contains two integers n and m (1 ≤ n ≤ 17, 1 ≤ m ≤ 105). The next line contains 2_n_ integers _a_1, a_2, ..., a_2_n (0 ≤ a__i < 230). Each of the next m lines contains queries. The i-th line contains integers p__i, b__i (1 ≤ p__i ≤ 2_n, 0 ≤ b__i < 230) — the i-th query.

第一行包含两个整数 $n$ 和 $m$（$1 ≤ n ≤ 17$，$1 ≤ m ≤ 10^5$）。
第二行包含 $2^n$ 个整数 $a_1, a_2, ..., a_{2^n}$（$0 ≤ a_i < 2^{30}$）。
接下来的 $m$ 行每行描述一个查询。第 $i$ 行包含两个整数 $p_i$、$b_i$（$1 ≤ p_i ≤ 2^n$，$0 ≤ b_i < 2^{30}$）—— 表示第 $i$ 个查询。

Print m integers — the i-th integer denotes value v for sequence a after the i-th query.

输出 m 个整数——第 i 个整数表示第 i 次查询后序列 a 的值 v。

For more information on the bit operations, you can follow this link: http://en.wikipedia.org/wiki/Bitwise_operation

有关位运算的更多信息，您可以点击此链接：http://en.wikipedia.org/wiki/Bitwise_operation