Problem Background

Xiao A enjoys problems involving range operations.

Problem Description

Xiao A has given you a sequence \( a \) of length \( n \), and \( q \) queries.

For each query, Xiao A will provide you with two positive integers \( l \) and \( 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 \) and \( q \).

The next line contains \( n \) integers \( a_i \).

The following \( q \) lines each contain two positive integers \( l \) and \( r \).

Output Format

There will be \( q \) lines in total.

Each line contains an integer representing your answer.

Sample Input and Output

Sample Input #1

6 1
1 1 4 5 1 4
1 6

Sample Output #1

18

Sample Input #2

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

Sample Output #2

11
0
20
8
21
8
23
25
24
11

Notes

[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 \).

Data Size and Constraints

This problem uses batched testing.

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

For all test cases, \( 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 a hack data set, reduced one data set.

见题面 Input 部分

见题面 Output 部分