题目描述

老师给文景出了一道题，希望文景能够锻炼一下位运算的能力，题目是：

给定 $2$ 的 $N$ 次方个数，组成的 $A$ 序列 $a[1] \sim a[N]$，按如下步骤进行计算：

1. 先两两按位求或，用“$|$”表示按位或，则计算为 $a[1]|a[2], a[3]|a[4], …, a[N-1]|a[N]$。

2. 第一步完成后，得到的 $B$ 序列 $b[1] \sim b[N/2]$，再两两按位异或，用“^”表示按位异或，则计算为$b[1]$^$b[2], b[3]$^$b[4], …, b[N/2-1]$^$b[N/2]$。

3. 重复 $1,2$ 两步，直到只剩下一个数为止。

文景很快就完成了计算，老师看到了答案后点了点头，随后在原来的 $a$ 序列中任选了一个数将其改变为了另一个值，再次交给文景去计算，但文景不负众望很快又给出了答案。老师觉得这样一个一个改太麻烦，于是干脆给出了 $M$ 个 $i$ 和 $x$，要求文景在每修改一个值后，都要给出计算后的结果。

文景这下傻眼了，于是他找到了你帮他计算结果。

格式

输入格式

第一行两个正整数 $N$ 和 $M$，中间用空格隔开。$（1≤N≤17；1≤M≤10^5）$

第二行 $2$ 的 $N$ 次方个数，用空格隔开，表示原始A序列$（0≤a[i]≤2^{30}）$

以下 $M$ 行，每行两个数 $i$ 和 $x$，中间用空格隔开，表示修改第i个数为 $x（0≤x≤2^{30}）$。

输出格式

对于每次修改后，输出一行，给出计算结果。

样例1

样例输入1

2 4
7 5 2 2
3 4
4 4
1 2
2 3

样例输出1

1
3
3
7

样例解释

第一次修改后序列为：$[7~5~4~2]$，先两两按位或得到 $[7~6]$，再两两按位异或得到 $[1]$；

第二次修改后序列为：$[7~5~4~4]$，先两两按位或得到 $[7~4]$，再两两按位异或得到 $[3]$；

第三次修改后序列为：$[2~5~4~4]$，先两两按位或得到 $[7~4]$，再两两按位异或得到 $[3]$；

第四次修改后序列为：$[2~3~4~4]$，先两两按位或得到 $[3~4]$，再两两按位异或得到 $[7]$；

限制

时间：$1s$ 空间：$256M$

对于 $30\%$ 的数据：$1≤N≤10；1≤M≤10^4；0≤a[i]≤2^{30}$；

对于 $100\%$ 的数据：$1≤N≤17；1≤M≤10^5；0≤a[i]≤2^{30}$；

来源

地址：$zloj,J2021$域
作者：$jialiang2509$