题目描述

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

给定 \(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\)