题目背景

在遥远的未来，人类建立了银河星轨计算阵列。阵列由 $n$ 个能量节点组成（$n$ 恰好为 $2$ 的整数次幂），每个节点存储着一个非负整数能量值。

相邻节点之间通过"能量门"连接，能量门按层级交替运算：

• 第 $1$ 层门做**按位与（AND）**运算
• 第 $2$ 层门做**按位或（OR）**运算
• 第 $3$ 层门做**按位与（AND）**运算
• 依此类推，交替进行

每次操作后，阵列最终会输出一个数值（根节点的值）。

题目描述

给定一个长度为 $n$ 的数组 $a$（$n = 2^k$），按上述规则逐层运算，最终得到一个值 $v$。

形式化地，定义 $a^{(0)} = a_1, a_2, \dots, a_n$ 为第 $0$ 层（输入层）。对于第 $t$ 层（$1 \le t \le k$），其长度为 $n / 2^t$，计算公式为：

$$a^{(t)}_i = \begin{cases} a^{(t-1)}_{2i-1} \ \&\ a^{(t-1)}_{2i}, & \text{若 } t \text{ 为奇数} \\[4pt] a^{(t-1)}_{2i-1} \ |\ a^{(t-1)}_{2i}, & \text{若 } t \text{ 为偶数} \end{cases}$$

最终 $v = a^{(k)}_1$。

现在有 $m$ 次修改操作，每次操作给定 $p$ 和 $b$，表示将 $a[p]$ 的值修改为 $b$。每次修改后，请输出新的最终值 $v$。

输入格式

第一行两个整数 $n, m$。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示初始数组。

接下来 $m$ 行，每行两个整数 $p, b$，表示将 $a[p]$ 修改为 $b$。

输出格式

对于每次修改，输出一行一个整数，表示修改后阵列的最终输出值。

样例

4 3
5 3 8 6
2 7
3 2
1 15

5
7
7

样例解释

初始 $a = [5,3,8,6]$：

第 $1$ 层（AND）：$5\ \&\ 3 = 1$，$8\ \&\ 6 = 0$

第 $2$ 层（OR）：$1\ |\ 0 = 1$

初始输出为 $1$。

---

第 $1$ 次修改：$a[2] = 7$，$a = [5,7,8,6]$

第 $1$ 层（AND）：$5\ \&\ 7 = 5$，$8\ \&\ 6 = 0$

第 $2$ 层（OR）：$5\ |\ 0 = 5$

输出 $5$。

---

第 $2$ 次修改：$a[3] = 2$，$a = [5,7,2,6]$

第 $1$ 层（AND）：$5\ \&\ 7 = 5$，$2\ \&\ 6 = 2$

第 $2$ 层（OR）：$5\ |\ 2 = 7$

输出 $7$。

---

第 $3$ 次修改：$a[1] = 15$，$a = [15,7,2,6]$

第 $1$ 层（AND）：$15\ \&\ 7 = 7$，$2\ \&\ 6 = 2$

第 $2$ 层（OR）：$7\ |\ 2 = 7$

输出 $7$。

数据范围和约定

测试点	$n$	$m$	说明
$1 \sim 8$	$n \le 2^6$	$m \le 60$	Part 1，暴力可过
$9 \sim 18$	$n \le 2^{17}$	$m \le 10^5$	Part 2，需线段树
$19 \sim 20$	特殊边界	—	全等值 / 最小规模

对于所有数据：$1 \le n \le 2^{17}$，$n = 2^k$（$k$ 为正整数），$1 \le m \le 10^5$，$0 \le a_i, b < 2^{30}$，$1 \le p \le n$。