E-异或和II_牛客练习赛153

时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$ 。
$\hspace{15pt}$ 你需要处理 $q$ 次操作，操作有以下两种：
$\hspace{23pt}\bullet$ $1\ x\ y$ ：将 $a_x$ 修改为 $y$ 。
$\hspace{23pt}\bullet$ $2\ k$ ：对于当前序列的每一个长度不超过 $k$ 的非空子序列，计算其中所有元素的按位或（Bitwise OR）值，并输出所有这些 OR 值的异或和。
$\hspace{15pt}$ 请你对于每个询问操作，输出对应的答案。

【名词解释】
$\hspace{15pt}$ 子序列：从原序列中删除任意个（可以为零，也可以为全部）元素，且保持剩余元素相对顺序不变得到的新序列。
$\hspace{15pt}$ 按位或（Bitwise OR）：对两个整数的二进制表示按位进行或运算。

$\hspace{15pt}$ 按位异或（Bitwise XOR）：对两个整数的二进制表示按位进行异或运算。

$\hspace{15pt}$ 在大部分情况下，PyPy 的运行速度优于 Python。本题我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行包含两个整数 ，分别表示序列长度和操作次数。
第二行包含  个整数 ，表示初始序列。
接下来  行，每行代表一次操作：
 输入三个整数 ：将  修改为 。
 输入两个整数 ：对于当前序列的每一个长度不超过  的非空子序列，计算其中所有元素的按位或（OR）值，并输出所有这些 OR 值的异或和。

除此之外，保证单个测试文件的  之和不超过 ， 之和不超过 。

输出描述:

对于每个询问操作，新起一行输出对应的答案。

示例1

输入

复制

输出

复制

3
7
6

说明

对于样例中的第一次询问 ，当前序列为 。
长度不超过  的所有非空子序列及其 OR 值分别为：
 ，OR 为 
 ，OR 为 
 ，OR 为 
 ，OR 为 
 ，OR 为 
 ，OR 为 
因此异或和为 。
修改后序列变为 。
对于第二次询问 ，所有长度不超过  的非空子序列的 OR 值异或和为 。
对于第三次询问 ，只需考虑长度为  的子序列，因此答案为 。