Range XOR and Set Update with Maximum XOR Query

You are given a sequence \(a_1, a_2, \dots, a_n\), where each \(a_i\) is a non-negative integer that is less than \(2^m\). You need to process \(q\) operations on the sequence. There are three types of operations:

• \(1\ x\ y\ w\): For every index \(i\) with \(x \le i \le y\), update \(a_i\) to \(a_i \operatorname{xor} w\). Here \(w\) is a non-negative integer less than \(2^m\).
• \(2\ x\ y\ w\): For every index \(i\) with \(x \le i \le y\), update \(a_i\) to \(w\). Here \(w\) is a non-negative integer less than \(2^m\).
• \(3\): Select a subset of \(\{a_1, a_2, \dots, a_n\}\) (possibly empty) such that the XOR sum of the selected numbers is maximized. Output this maximum value. The XOR sum of \(x_1, x_2, \dots, x_l\) is defined as \(x_1 \operatorname{xor} x_2 \operatorname{xor} \dots \operatorname{xor} x_l\).

Implement these operations and answer all the type \(3\) queries.

inputFormat

The input begins with a line containing three integers \(n\), \(m\), and \(q\).

The second line contains \(n\) space-separated non-negative integers \(a_1, a_2, \dots, a_n\), each less than \(2^m\).

The following \(q\) lines each describe an operation in one of the following formats:

• \(1\ x\ y\ w\)
• \(2\ x\ y\ w\)
• \(3\)

Note: For operations of type 1 and 2, the range \([x, y]\) is 1-indexed.

outputFormat

For each operation of type \(3\), output the maximum XOR sum obtained, each on a separate line.

sample

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

7
7
3