P5670 Secret Manual - Repeated XOR

Given a sequence of length $n$, support the following operations: - `1 l r x`: Add $x$ to all elements in the interval $[l, r]$. - `2 l r`: Query the value of the last $m$ binary bits of the XOR sum of all elements in the interval $[l, r]$.

The first line contains three positive integers $n, m, q$, representing the sequence length, the number of bits, and the number of operations. The second line contains $n$ non-negative integers, representing the original sequence $a_i$. The next $q$ lines each contain several non-negative integers describing an operation.

For each operation of type `2`, output one line containing a non-negative integer representing the answer.

Constraints This problem has $10$ test points. For test points $1 \sim 3$, $1 \le n, q \le 1000$. For test points $4, 5$, $1 \le m \le 5$. For test points $6 \sim 10$, let $k$ be the test point index, then $m = k$. For $100\%$ of the testdata, $1 \le n, q \le 10^5$, $1 \le m \le 10$, and $0 \le a_i, x < 2^m$. **Please pay attention to constant optimization.** Translated by ChatGPT 5