← 返回题目列表

Codeforces · 339/D

D. Xenia 和位操作

中文机器翻译题面 查看原题

初级程序员 Xenia 有一个序列 a,由 2n 个非负整数组成:a1, a2, ..., a2n。 Xenia 目前正在研究位运算。为了更好地理解它们的工作原理,Xenia 决定计算 a 的某个值 v。

也就是说,需要多次迭代来计算值 v。在第一次迭代时,Xenia 写入一个新序列 a1 或 a2、a3 或 a4、...、a2n - 1 或 a2n,由 2n - 1 个元素组成。换句话说,她写下了序列 a 的相邻元素的按位或。在第二次迭代时,Xenia 写入第一次迭代后获得的序列的相邻元素的按位异或。在第三次迭代时,Xenia 写入第二次迭代后获得的序列的相邻元素的按位或。等等;按位异或和按位或交替进行。最后,她得到了一个由一个元素组成的序列,该元素就是v。

让我们考虑一个例子。假设序列 a = (1, 2, 3, 4)。然后我们写下所有的变换 (1, 2, 3, 4) → (1 or 2 = 3, 3 or 4 = 7) → (3 xor 7 = 4)。结果是 v = 4。

你得到了 Xenia 的初始序列。但是计算给定序列的值 v 太容易了,因此您需要额外的 m 个查询。每个查询都是一对整数 p、b。查询p,b意味着需要执行赋值ap = b。每次查询后,您需要打印新序列 a 的新值 v。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 17, 1 ≤ m ≤ 105)。下一行包含 2n 个整数 a1, a2, ..., a2n (0 ≤ ai < 230)。接下来的 m 行中的每一行都包含查询。第 i 行包含整数 pi, bi (1 ≤ pi ≤ 2n, 0 ≤ bi < 230) — 第 i 个查询。

输出

打印 m 个整数 — 第 i 个整数表示第 i 个查询后序列 a 的值 v。

示例

输入 #1

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

输出 #1

1
3
3
3

注意

有关位运算的更多信息,您可以点击以下链接:http://en.wikipedia.org/wiki/Bitwise_operation