Gravitational Wave Frequency Summation

Geopelia needs to capture a special type of gravitational wave with a frequency that is different from that produced by black holes.

The (i)-th gravitational wave has a frequency (A_i). When multiple gravitational waves overlap, their frequencies combine via the bitwise OR operation. For a sequence (A) of length (n), the combined frequency of all gravitational waves in (A) is defined as [ f(A)=\bigcup_{i=1}^n A_i, ] where (\bigcup) denotes the bitwise OR operation.

Geopelia is interested in queries of the form [ \sum_{i=l}^r \left( \bigcup_{j=l}^i A_j \right), ] where (A[l, r]) denotes the subarray (A_l, A_{l+1}, \dots, A_r).

However, due to the gravitational influence of the azure boundary, an interval ([l, r]) might have its frequencies affected by a bitwise XOR with a given value (x).

Formally, you are given an array (A) of length (n) and (q) operations. Each operation is either:

1. (1\ l\ r\ x): For every index (i) with (l \le i \le r), update (A_i := A_i \oplus x) (where (\oplus) denotes the bitwise XOR).
   
   
2. (2\ l\ r): Compute and output [ \left( \sum_{i=l}^r \bigcup_{j=l}^i A_j \right) \bmod 2^{30}, ] where the bitwise OR is used to combine elements in each prefix of the subarray.
   
   Note: Since the frequencies may be very high, you only need to report the answer modulo (2^{30}).

inputFormat

The first line contains two integers (n) and (q), representing the number of elements in the array and the number of operations, respectively.

The second line contains (n) integers (A_1, A_2, \dots, A_n), denoting the initial array.

Each of the following (q) lines describes an operation, which can be one of the following two types:

1. For an update: 1 l r x meaning that for each (i) ((l \le i \le r)) you should perform (A_i := A_i \oplus x).
   
   
2. For a query: 2 l r asking you to compute [ \left( \sum_{i=l}^r \bigcup_{j=l}^i A_j \right) \bmod 2^{30}. ] All indices are 1-indexed.

outputFormat

For each operation of type 2, output the computed result on a separate line. The result should be given modulo (2^{30}).

sample

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

7
17