Description

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]$.

Input Format

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.

Output Format

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

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

1
0
3
1
3

Hint

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