Background

Special for beginners, ^_^

Description

在课堂上，徐老师向同学们介绍了一种特殊的运算 —— 异或 (XOR)。 它的运算规则是：

• 相同为 0，不同为 1。 例如：
• $5 \oplus 5 = 0$
• $5 \oplus 7 = 2$

为了考验大家的理解，徐老师在黑板上写下了一个长度为 $n$ 的整数数组，并多次提问： “从第 $l$ 个数到第 $r$ 个数，这一段数的异或和是多少？”

异或和的定义是：

$$\text{xor}(l,r) = a_l \oplus a_{l+1} \oplus \dots \oplus a_r $$

请你写一个程序，帮助徐老师快速回答这些问题。

---

Format

输入：

• 第一行两个整数 $n,q$ $(1 \leq n,q \leq 10^5)$，分别表示数组长度和询问次数。
• 第二行包含 $n$ 个整数 $0 \leq a_i < 2^{31}$，表示数组的元素。
• 接下来 $q$ 行，每行两个整数 $l,r$ $(1 \leq l \leq r \leq n)$，表示一个查询区间。

输出：

• 共 $q$ 行，每行一个整数，表示对应区间的异或和。

---

Sample

5 3
1 2 3 4 5
1 3
2 4
1 5

0
5
1