题目描述

给定序列 $a_1, a_2, \dots, a_n$，共 $m$ 次询问。每次询问给出区间 $[l, r]$，需计算所有满足 $l \le L \le R \le r$ 的子区间 $(L, R)$ 的权值的按位异或和。其中，子区间 $(L, R)$ 的权值定义为该子区间内不同元素的个数，即 $|\{a_i \mid L \le i \le R\}|$。

输入格式

从标准输入读入数据，格式如下：

1. 第一行：两个整数 $n$ 和 $m$（分别表示序列长度和询问次数）；
2. 第二行：$n$ 个整数 $a_1, a_2, \dots, a_n$（表示给定的序列）；
3. 接下来 $m$ 行：每行两个整数 $l$ 和 $r$（表示一次询问的区间）。

输出格式

输出到标准输出，共 $m$ 行。每行对应一次询问的结果，即该询问区间内所有子区间权值的按位异或和。

样例

输入

5 2
1 1 1 2 4
1 5
3 5

输出

3
2

样例解释

1. 对于第一次询问 $[1, 5]$：
   • 所有子区间的权值及异或和计算如下：
     • 长度为 1 的子区间：权值均为 1（共 5 个），异或和为 $1 \oplus 1 \oplus 1 \oplus 1 \oplus 1 = 1$；
     • 长度为 2 的子区间：权值为 1、1、2、2（共 4 个），异或和叠加后为 $1 \oplus 1 \oplus 2 \oplus 2 = 0$，累计异或和仍为 1；
     • 长度为 3 的子区间：权值为 1、2、2（共 3 个），异或和叠加后为 $1 \oplus 2 \oplus 2 = 1$，累计异或和为 $1 \oplus 1 = 0$；
     • 长度为 4 的子区间：权值为 2、2（共 2 个），异或和叠加后为 $2 \oplus 2 = 0$，累计异或和仍为 0；
     • 长度为 5 的子区间：权值为 3（共 1 个），异或和叠加后为 3，最终累计异或和为 $0 \oplus 3 = 3$。
2. 对于第二次询问 $[3, 5]$：
   • 所有子区间的权值及异或和计算如下：
     • 长度为 1 的子区间：权值均为 1（共 3 个），异或和为 $1 \oplus 1 \oplus 1 = 1$；
     • 长度为 2 的子区间：权值为 1、2（共 2 个），异或和叠加后为 $1 \oplus 2 = 3$，累计异或和为 $1 \oplus 3 = 2$；
     • 长度为 3 的子区间：权值为 2（共 1 个），异或和叠加后为 2，最终累计异或和为 $2 \oplus 2 = 2$。

数据范围与提示