C. Phonier
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$a$$$ of length $$$n$$$, you need to answer $$$m$$$ queries.

Each query will provide $$$l$$$ and $$$r$$$, and you need to calculate the value of $$$\bigoplus\limits_{i=l}^{r}\bigoplus\limits_{j=l}^{r}(a_i+a_j)$$$, the bitwise XOR of all $$$a_i+a_j$$$ such that $$$l \le i, j \le r$$$.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 10^6$$$) — the length of the array $$$a$$$ and the number of queries.

The second line contains $$$n$$$ integers $$$a_1,a_2 \ldots a_n$$$ $$$(0 \leq a_i \leq 10^9)$$$ — the elements of the array $$$a$$$.

Then, there are $$$m$$$ lines, each containing two integers $$$l$$$ and $$$r$$$ $$$(1 \leq l \leq r \leq n)$$$.

—

Tests in subtasks are numbered from $$$1 - 10$$$ with samples skipped. Each test is worth $$$\frac{100}{10}=10$$$ points.

Tests $$$1 - 2$$$ satisfy $$$1 \leq n, m \leq 100$$$.

Tests $$$3 - 5$$$ satisfy $$$1 \leq n, m \leq 3366$$$.

The remaining tests do not satisfy any additional constraints.

Output

Output $$$m$$$ lines, each containing an integer, representing the answer to each query.

Example
Input
5 4
0 1 2 3 4
3 5
2 2
1 4
1 5
Output
10
2
0
8
Note

The answer to the first query of the sample test is $$$(2+2) \oplus (2+3) \oplus (2+4) \oplus (3+2) \oplus (3+3) \oplus (3+4) \oplus (4+2) \oplus (4+3) \oplus (4+4)$$$, which simplifies to $$$4 \oplus 5 \oplus 6 \oplus 5 \oplus 6 \oplus 7 \oplus 6 \oplus 7 \oplus 8=10$$$.

—

Problem Idea: willy108

Problem Preparation: willy108

Occurrences: Novice C