XOR Subset Query and Update

You are given an integer sequence \(a_1, a_2, \ldots, a_n\) of length \(n\). You need to process \(m\) operations on the sequence. Each operation is represented by four integers \(opt\), \(l\), \(r\), \(v\), and is one of the following types:

• When \(opt = 1\): For every index \(i\) in the range \([l,r]\), update \(a_i\) as \(a_i = a_i \oplus v\), where \(\oplus\) denotes the bitwise XOR operation.
• When \(opt = 2\): Query the subarray \(a_l, a_{l+1}, \ldots, a_r\). You are allowed to pick any subset of these numbers (possibly empty) and take their XOR sum. Let this XOR sum be \(X\). Your task is to compute the maximum possible value of \(X \oplus v\) over all subsets (recall that the XOR of an empty set is 0).

Note: All formulas are represented in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(m\), representing the length of the sequence and the number of operations, respectively.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) separated by spaces.

Each of the following \(m\) lines contains four integers \(opt, l, r, v\) describing an operation.

outputFormat

For each query operation (i.e. when \(opt = 2\)), output the maximum value of \(X \oplus v\) on a separate line, where \(X\) is any XOR combination of a subset of the subarray \(a_l, a_{l+1}, \ldots, a_r\).

sample

3 3
1 2 3
2 1 3 0
1 2 2 1
2 2 3 1

3
2