题目描述

给定一个长度为 $n$ 的数列 $a$，有 $q$ 次询问。每次询问给定两个整数 $l, r$，请求出 $a_l \oplus a_{l+1} \oplus \cdots \oplus a_r$ 的值，即第 $l$ 个数到第 $r$ 个数的按位异或和。

其中 $\oplus$ 表示按位异或运算（C++ 中为 ^ 运算符）。

输入格式

第一行两个整数 $n, q$，表示数列长度和询问次数。

第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$。

接下来 $q$ 行，每行两个整数 $l, r$，表示一次询问。保证 $1 \le l \le r \le n$。

输出格式

共 $q$ 行，第 $i$ 行输出第 $i$ 次询问的答案。

说明/提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1 \le n, q \le 10^5$，$0 \le a_i \le 10^9$。

本题为本校训练自编题（参照经典题型）。