Range Addition and XOR Query with Bit Extraction

Given an integer sequence \(a_1, a_2, \dots, a_n\) of length \(n\) initially filled with 0, you need to support the following operations:

• \(1\; l\; r\; x\): Add an integer \(x\) to every element in the interval \([l, r]\).
• \(2\; l\; r\): Compute the bitwise XOR of all elements in the interval \([l, r]\) and output the value represented by its last \(m\) binary digits (i.e. the result modulo \(2^m\)).

You are given \(q\) operations to process sequentially. For each operation of type 2, output the result as described.

inputFormat

The first line contains three integers \(n, q, m\) \( (1 \le n, q \le 10^5, 1 \le m \le 32)\) — the length of the sequence, the number of operations, and the number of binary digits to output.

Each of the next \(q\) lines describes an operation in one of the following formats:

• \(1\; l\; r\; x\) — add \(x\) to every element in the subarray \([l, r]\) (\(1 \le l \le r \le n\), \(|x| \le 10^9\)).
• \(2\; l\; r\) — output the last \(m\) binary digits of the bitwise XOR of the subarray \([l, r]\) (\(1 \le l \le r \le n\)).

outputFormat

For each query operation (type 2), output a single integer representing the last \(m\) binary digits of the bitwise XOR of the corresponding subarray.

sample

5 5 3
1 1 3 1
2 2 5
1 2 4 2
2 1 5
2 3 3

0
3
3