简单异或题

题号：NC311952
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给出一个长度为 $n\times m$ 的数组 $a_1,a_2,\dots,a_{n\times m}$ ，它是由一个长度为 $n$ 的数组 $b_1,b_2,\dots,b_n$ 重复 $m$ 次生成的，且每一次重复后，数组 $b$ 的每一个元素都加上 $1$ 。换句话说，数组 $a$ 由 $m$ 个块拼接而成，其中第 $i \left(1 \le i \le m\right)$ 个块由数组 $b$ 的每个元素加上 $i-1$ 构成。
$\hspace{15pt}$ 例如，若数组 $b$ 为 $\{4,7\}$ ，重复 $2$ 次后，数组 $a$ 为 $\{4,7,5,8\}$ 。

$\hspace{15pt}$ 设 $f_{1,j}= \begin{cases} <br />a_j & 1\le j\le n\times m \\<br />0& n\times m < j<br />\end{cases}$ ，对于 $2 \le i$ 且 $1 \le j$ ，有 $f_{i,j}=f_{i-1,j}\oplus f_{i-1,j+1}$ 。

$\hspace{15pt}$ 现在有 $Q$ 个查询，每次询问给出三个数 $k_i,l_i,r_i$ ，询问 $\displaystyle\bigoplus_{j=l_i}^{r_i}f_{k_i,j} = f_{k_i,l_i} \oplus f_{k_i,l_i+1} \oplus \cdots \oplus f_{k_i,r_i}$ 的值。

【名词解释】
$\hspace{15pt}$ $\oplus$ ：指位运算中的按位异或（Bitwise XOR），对两个整数的二进制表示按位进行异或运算。

输入描述:

第一行输入两个整数 ，表示数组  中的元素数量、数组  的重复次数。
第二行输入  个整数 ，表示数组  中的元素。
第三行输入一个整数 ，表示查询次数。
此后  行，第  行输入三个整数 ，表示第  次查询的参数。

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

输出描述:

对于每一次查询，新起一行输出一个整数表示答案。

示例1

输入

复制

输出

复制

7
6

示例2

输入

复制

输出

复制

1
15
13

备注:

本题数据量较大，我们建议您选取较快的读入方式。