Problem Description

Given a sequence $a_1,\dots,a_n$ and a total of $m$ queries, each query provides $l,r$. You need to compute the bitwise XOR sum of the weights of all pairs $(L,R)$ that satisfy $l\le L\le R\le r$. The weight of a pair $(L,R)$ is $|\{a_i\mid L\le i\le R\}|$.

Input Format

Read from standard input.

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

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

The next $m$ lines each contain two integers $l\ r$, representing one query.

Output Format

Write to standard output.

Output $m$ lines, in order, each being the answer to the corresponding query.

5 2
1 1 1 2 4
1 5
3 5

3
2

Hint

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

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

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

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

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

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

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

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

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

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

Each category of testdata forms a subtask.

Translated by ChatGPT 5