Background

Little A likes interval operation problems.

Problem Description

Little A gives you a sequence $a$ of length $n$, and $q$ queries.

For each query, Little A gives you two positive integers $l, r$. You need to compute the value of $(a_l) \oplus (a_l+a_{l+1}) \oplus (a_l+a_{l+1}+a_{l+2}) \oplus \dots \oplus (a_l + a_{l+1} + a_{l+2} + \dots + a_r)$.

Here $\oplus$ denotes the XOR operation.

Input Format

The first line contains two positive integers $n, q$.

The next line contains $n$ integers $a_i$.

Then follow $q$ lines, each containing two positive integers $l, r$.

Output Format

Output $q$ lines.

Each line contains one integer, representing your answer.

6 1
1 1 4 5 1 4
1 6

18

7 10
1 9 1 9 8 1 0
1 2
1 3
1 4
1 5
1 6
1 7
2 6
3 5
4 7
2 7

11
0
20
8
21
8
23
25
24
11

Hint

[Sample Explanation #1]

$1 \oplus (1 + 1) \oplus (1 + 1 + 4) \oplus (1 + 1 + 4 + 5) \oplus (1 + 1 + 4 + 5 + 1) \oplus (1 + 1 + 4 + 5 + 1 + 4) = 18$.

Constraints and Notes

This problem uses bundled tests.

• Subtask 0 (13 pts): $n, q \le 10^2$.
• Subtask 1 (28 pts): $n, q \le 10^4$.
• Subtask 2 (19 pts): $a_i \le 10^4$.
• Subtask 3 (7 pts): $n \le 10^2$.
• Subtask 4 (17 pts): all $a_i$ are non-negative powers of $2$.
• Subtask 5 (16 pts): no special constraints.

For all testdata, $1 \le l \le r \le n \le 10^4$, $1 \le q \le 10^6$, $0 \le a_i \le 10^{10}$.

upd (2024.7.3): Added one set of hack testdata, removed one set of testdata.

Translated by ChatGPT 5