Nim Multiplication Operations

Given two non‐negative integers (a) and (b), define their nim product as (a \otimes b = \operatorname{mex}({(a \otimes d) \oplus (c \otimes b) \oplus (c \otimes d) \mid 0 \le c < a,; 0 \le d < b})), where (x \oplus y) denotes the bitwise XOR of (x) and (y), and (\operatorname{mex}(S)) is the smallest non‐negative integer not contained in (S).

You are given a sequence of (n) non‐negative integers (a_1, a_2, \ldots, a_n) and (q) operations. Each operation is described by three integers (t, \ell, r):

• If \(t = 1\), then for every index \(i\) with \(\ell \leq i \leq r\) update \(a_i \gets a_i \otimes a_i\) (that is, square it under nim multiplication).
• If \(t = 2\), output the bitwise XOR \(a_\ell \oplus a_{\ell+1} \oplus \cdots \oplus a_r\).
• If \(t = 3\), output the sum \(a_\ell + a_{\ell+1} + \cdots + a_r\).

Output the answer for each query of type 2 or 3 on a separate line.
Note: All formulas are represented in \(\LaTeX\) format.

inputFormat

The first line contains two integers (n) and (q), the number of elements and the number of operations respectively. The second line contains (n) non-negative integers (a_1, a_2, \ldots, a_n). Each of the next (q) lines contains three integers (t), (\ell) and (r) describing an operation as follows:

• \(t = 1\): Update each \(a_i\) for \(\ell \leq i \leq r\) to \(a_i \gets a_i \otimes a_i\).
• \(t = 2\): Query the value of \(a_\ell \oplus a_{\ell+1} \oplus \cdots \oplus a_r\).
• \(t = 3\): Query the value of \(a_\ell + a_{\ell+1} + \cdots + a_r\).

All indices are 1-based.

outputFormat

For each operation of type 2 or 3, output the answer on a separate line.

sample

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

0
0
4

</p>