Range XOR Queries

Difficulty: 1300 3000 ms 128 MB

bitwise prefix-sums

Each query gives L and R and asks for a_L ⊕ a_L+1 ⊕ … ⊕ a_R.

Input: the first line has N and Q; the second line has N non-negative integers; each of the next Q lines has L and R.

Output: Q lines — the XOR of each range.

Constraints:

• 1 ≤ N, Q ≤ 10⁴
• 0 ≤ a_i ≤ 10⁹

Sample Tests

4 2
1 2 3 4
1 2
2 4

3
5

1 1
9
1 1

9

Read the Editorial