Given a sequence $a_1, \dots, a_n$, there are $m$ queries. Each query provides $l, r$, and you are to calculate the bitwise XOR sum of the weights of all pairs $(L, R)$ such that $l \le L \le R \le r$. The weight of a pair $(L, R)$ is defined as $|\{a_i \mid L \le i \le R\}|$ (the number of distinct elements in the subarray from index $L$ to $R$).

Input

The first line contains two integers $n$ and $m$.

The next line contains $n$ integers $a_1, \dots, a_n$.

The next $m$ lines each contain two integers $l$ and $r$, representing a query.

Output

Output $m$ lines, each containing the answer to the corresponding query.

Examples

Input 1

5 2
1 1 1 2 4
1 5
3 5

Output 1

3
2

Subtasks

For $5\%$ of the data, $1 \le n, m \le 100$.

For $10\%$ of the data, $1 \le n, m \le 5000$.

For $20\%$ of the data, $1 \le n, m \le 10^5$.

For $30\%$ of the data, $1 \le n, m \le 2 \times 10^5$.

For $40\%$ of the data, $1 \le n, m \le 3 \times 10^5$.

For $50\%$ of the data, $1 \le n, m \le 3.5 \times 10^5$.

For another $10\%$ of the data, $m = n^2$.

For another $10\%$ of the data, $a_i \le 2$ for all $i = 1 \dots n$.

For another $10\%$ of the data, $a_i \le 10$ for all $i = 1 \dots n$.

For $100\%$ of the data, $1 \le n, m \le 4 \times 10^5$, $1 \le a_i \le n$, and all values are integers.

Each category of data constitutes a subtask.