题目描述

xenia 是一名初级程序员，他有一个由 \(2^n\) 个非负整数的序列 a：\(a_1\), \(a_2\),…, \(a_{2^n}\)。xenia 目前正在研究位运算，为了更好的了解它们的工作，xenia 打算去计算某些值 v。他需要多次运算才能得到 v 值。
例如序列 a = {1, 2, 3, 4}：
第一步：将相邻元素进行 OR 运算，(1 or 2 = 3, 3 or 4 = 7)；
第二步：将相邻元素进行 XOR 运算，(3 xor 7 = 4)；
第三步：重复 2, 3 步，直到得到 v。
简单来说就是 OR, XOR 这两种运算符的交替运算，然后输出最终的数值。
再给出 m 个更新，每次更新一对整数 p, b，将 p 位置的值改为 b。对于每次更新，输出整个序列的 v 值。

输入格式

第一行两个整数 n, m；
第二行 \(2^n\) 个整数 \(a_1\), \(a_2\), …, \(a_{2^n}\)；
接下来 m 个更新 \(p_i\), \(b_i\)。

输出格式

对于每个更新，输出整个序列的 v 值。

样例1

输入

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

输出

1
3
3
3

数据范围

对于 30%的数据，1 \(\leq\) n \(\leq\) 5, 1 \(\leq\) m \(\leq\) 20，0 \(\leq\) ai < 50，1 \(\leq\) \(p_i\) \(\leq\) \(2^n\), 0 \(\leq\) \(b_i\) < 50；
对于 100%的数据，1 \(\leq\) n \(\leq\) 17, 1 \(\leq\) m \(\leq\) \(10^5\)，0 \(\leq\) \(a_i\) < 230，1 \(\leq\) \(p_i\) \(\leq\) \(2^n\), 0 \(\leq\) \(b_i\) < \(2^{30}\)。

限制

1s, 256M

来源

Codeforces339D
CWOI新高二专题测试十五