SP28352 FRNDZND - Friend Zoned

Pavel 想要向心上人求婚，但她没有立即答应，而是给了他一个有 $N$ 个整数的数组，并要求他回答 $M$ 个关于这个数组的查询。每个查询由两个整数 $L$ 和 $R$ 组成。 对于每一个查询，Pavel 需要进行以下步骤： 1. 从数组中选取索引为 $L$ 到 $R$ 的元素，将它们插入到一个多重集合中。多重集合允许重复元素存在。假设插入之后，多重集合的大小为 $k$，也就是 $k = R - L + 1$。 2. 接下来，他要生成这个多重集合的所有可能子集（包括空集）。对于每一个子集，计算子集中所有元素的异或值。这样可以得到 $2^k$ 个不同的异或值。请注意，对于空集，异或值为 $0$。 3. 最后，将这 $2^k$ 个异或值进行一次总的异或运算，得到的结果就是他的回答。 如果 Pavel 能够正确回答所有的查询，她将会重新考虑这段关系。你能帮助他解决这些问题吗？

第一行输入两个整数 $N$ 和 $Q$。第二行包含 $N$ 个整数，这些数构成了数组。接下来的 $Q$ 行，每行包含两个整数 $L$ 和 $R$，代表一个查询。

对每个查询输出一个整数，分别表示对应查询的答案。输出顺序应与输入顺序相同。

- $1 \le N, Q \le 10^5$ - $1 \le L \le R \le N$ - $0 \le 数组中的数 \le 10^9$ **本翻译由 AI 自动生成**