给定序列 $a_1,\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\}|$。

输入格式

从标准输入读入数据。

第一行两个整数 $nm$；

接下来一行 $n$ 个整数 $a_1,\dots ,a_n$；

接下来 $m$ 行，每行两个整数 $lr$ 表示一次查询。

输出格式

输出到标准输出。

输出 $m$ 行，依次表示每个询问的答案。

样例 1

input

5 2
1 1 1 2 4
1 5
3 5

output

3
2

子任务

对于 $5\mathrm{\%}$ 的数据，满足 $1\le n,m\le 100$。

对于 $10\mathrm{\%}$ 的数据，满足 $1\le n,m\le 5000$。

对于 $20\mathrm{\%}$ 的数据，满足 $1\le n,m\le {10}^5$。

对于 $30\mathrm{\%}$ 的数据，满足 $1\le n,m\le 2\times {10}^5$。

对于 $40\mathrm{\%}$ 的数据，满足 $1\le n,m\le 3\times {10}^5$。

对于 $50\mathrm{\%}$ 的数据，满足 $1\le n,m\le 3.5\times {10}^5$。

对于另外 $10\mathrm{\%}$ 的数据，满足 $m=n^2$。

对于另外 $10\mathrm{\%}$ 的数据，满足对任意 $i=1\cdots n$，$a_i\le 2$。

对于另外 $10\mathrm{\%}$ 的数据，满足对任意 $i=1\cdots n$，$a_i\le 10$。

对于 $100\mathrm{\%}$ 的数据，满足 $1\le n,m\le 4\times {10}^5$，$1\le a_i\le n$，所有数值为整数。

每类数据构成子任务。

时间限制：10s 12s

空间限制：512MB