给出一个长度为 的数组 ，它是由一个长度为 的数组 重复 次生成的，且每一次重复后，数组 的每一个元素都加上 。换句话说，数组 由 个块拼接而成，其中第 个块由数组 的每个元素加上 构成。 例如，若数组 为 ，重复 次后，数组 为 。 设 a_j & 1\le j\le n\times m \\0& n\times m \end{cases}" ，对于 且 ，有 。 现在有 个查询，每次询问给出三个数 ，询问 的值。 【名词解释】 ：指位运算中的按位异或（Bitwise XOR），对两个整数的二进制表示按位进行异或运算。

输入描述:

第一行输入两个整数 ，表示数组 中的元素数量、数组 的重复次数。第二行输入 个整数 ，表示数组 中的元素。第三行输入一个整数 ，表示查询次数。此后 行，第 行输入三个整数 ，表示第 次查询的参数。除此之外，保证单个测试文件的 之和不超过 。

输出描述:

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

备注:

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