P10401 "XSOI-R1" Interval Operations (opt)

Little A likes interval operation problems.

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.

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 $q$ lines. Each line contains one integer, representing your answer.

**[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