$\text{Ysgg}$ 得到了一个长度为 $2^n$ 的非负整数序列 $a$。

他定义了一种特殊的合并方式。

首先，将序列中相邻的两个数进行按位或（OR）运算，得到一个长度减半的新序列；然后，将新序列中相邻的两个数进行按位异或（XOR）运算，再得到一个长度减半的新序列。

之后继续交替进行这两种运算：

• 第 $1$ 次合并使用按位或（OR）；
• 第 $2$ 次合并使用按位异或（XOR）；
• 第 $3$ 次合并再次使用按位或（OR）；
• 第 $4$ 次合并再次使用按位异或（XOR）；
• 以此类推。

经过恰好 $n$ 次合并后，整个序列最终只剩下一个整数，将这个整数记为 $v$。

现在，$\text{Ysgg}$ 将对序列进行 $m$ 次修改。第 $i$ 次修改会给出两个整数 $p_i$ 和 $b_i$，表示将当前序列中的 $a_{p_i}$ 修改为 $b_i$。

每次修改结束后，请你求出当前序列按照上述规则合并后得到的整数 $v$。

输入

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 17$，$1 \le m \le 10^5$），分别表示序列长度的指数以及修改次数。序列的实际长度为 $2^n$。

第二行包含 $2^n$ 个整数 $a_1,a_2,\ldots,a_{2^n}$（$0 \le a_i < 2^{30}$），表示初始序列。

接下来 $m$ 行，第 $i$ 行包含两个整数 $p_i$ 和 $b_i$（$1 \le p_i \le 2^n$，$0 \le b_i < 2^{30}$），表示第 $i$ 次修改将 $a_{p_i}$ 改为 $b_i$。

输出

对于每次修改，输出一行一个整数，表示修改完成后当前序列最终合并得到的整数 $v$。

样例

Input1

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

Output1

1
3
3
3

说明

初始序列为 $[1,6,3,5]$。

由于 $n=2$，每次需要进行两层合并：第一层使用按位或，第二层使用按位异或。

第一次修改后，序列变为 $[4,6,3,5]$。

第一层合并得到：

• $4\operatorname{OR}6=6$；
• $3\operatorname{OR}5=7$。

第二层合并得到：

$$6\operatorname{XOR}7=1.$$

因此第一次修改后的答案为 $1$。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 17$；
• $1 \le m \le 10^5$；
• $0 \le a_i,b_i < 2^{30}$；
• $1 \le p_i \le 2^n$。

本题共有 $20$ 个测试点，每个测试点 $5$ 分。

特殊性质：

• 性质 A：$m=1$；
• 性质 B：$n=1$；
• 性质 C：所有修改操作中的 $p_i$ 均相同；
• 性质 D：所有 $a_i$ 和 $b_i$ 均属于集合 $\{0,1\}$。

测试点编号	$n$	$m$	特殊性质
$1$	$\le 2$	$\le 5$	无
$2$	$\le 4$	$\le 20$
$3\sim4$	$\le 8$	$\le 100$
$5\sim6$	$\le 10$	$\le 1000$
$7$	$\le 17$	$1$	A
$8$	$1$	$\le 10^5$	B
$9$	$\le 17$		C
$10$			D
$11\sim12$	$\le 12$	$\le 10^4$	无
$13\sim14$	$\le 15$	$\le 5\times 10^4$
$15\sim20$	$\le 17$	$\le 10^5$