当前没有测试数据。

4.和或异或

题目描述

小明找来了一个$2^{n}$长度的数组。它第一次先对所有相邻两个数执行操作，得到一个$2^{n-1}$长度的数组。也就是说，如果一开始时$a[1],a[2],\ldots,a[2^n]$，执行操作后，会得到$a[1] \mid a[2],a[3] \mid a[4],\ldots,a[2^n-1] \mid a[2^n]$。

第二次操作，小明会将所有相邻两个数执行$\wedge$操作，得到一个$2^{n-2}$长度的数组，假如第一次操作后的数组是$b[1],b[2],\ldots,b[2^{n-1}]$，执行操作后会变成$b[1] \wedge b[2],b[3] \wedge b[4],\ldots,b[2^{n-1}-1] \wedge b[2^{n-1}]$。

第三次操作，小明仍然将执行$\mid$操作，第四次小明执行$\wedge$操作。如此交替进行。

小明还会执行$Q$次修改操作。每次修改原先的$2^{n}$长度的数组中的某一个数，对于每次修改操作，你需要输出$n$次操作后（最后一定只剩下唯一一个数）剩下的那个数是多少。

输入格式

第一行两个数$n$，$Q$。

接下来一行$2^{n}$个数$a$，表示一开始的数组。

接下来$Q$行，每行两个数$x_i$，$y_i$，表示小明这次的修改操作是将$a_{x_i}$改成$y_i$。

输出格式

$Q$行，表示每次修改操作后执行$n$次操作后剩下的那个数的值。

数据范围与提示

• 对于$30\%$的数据，$n \leq 17$，$Q = 1$；
• 对于另外$20\%$的数据，$n \leq 10$，$Q \leq 1000$；
• 对于再另外$30\%$的数据，$n \leq 12$，$Q \leq 100000$；
• 对于$100\%$的数据，$1 \leq n \leq 17$，$1 \leq Q \leq 10^{5}$，$1 \leq x_i \leq 2^{n}$，$0 \leq y_i < 2^{30}$，$0 \leq a_i < 2^{30}$。

样例

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

1
3
3
3

说明

第一次修改，$4$，$6$，$3$，$5$ $\rightarrow$ $6$，$7$ $\rightarrow$ $1$。

第二次修改，$4$，$6$，$4$，$5$ $\rightarrow$ $6$，$5$ $\rightarrow$ $3$。

第三次修改，$2$，$6$，$4$，$5$ $\rightarrow$ $6$，$5$ $\rightarrow$ $3$。

第四次修改，$2$，$6$，$4$，$5$ $\rightarrow$ $6$，$5$ $\rightarrow$ $3$。