Online Sequence Manipulation

You are given an array \(a_1, a_2, \dots, a_n\) and \(q\) operations. All operations and the final output should be computed modulo \(10^9+7\). This problem is online which means that for each operation, all parameters except the first one (the operation type) are given in an encoded form: the actual parameter is obtained by taking the bitwise XOR with \(last\), where \(last\) is the answer (modulo \(10^9+7\)) from the previous query of type \(1\) (initially \(last = 0\)).

The operations are defined as follows:

• 1 l r: Output the sum of the subarray \(a_l, a_{l+1}, \dots, a_r\). After this operation, update \(last\) to be this answer modulo \(10^9+7\).
• 2 l r k: Assign \(a_i = k\) for all \(l \le i \le r\).
• 3 l r k: Add \(k\) to each \(a_i\) for \(l \le i \le r\), i.e., \(a_i = a_i + k\).
• 4 l_1 r_1 l_2 r_2: Copy the subarray \(a_{l_1}, \dots, a_{r_1}\) to the segment \(a_{l_2}, \dots, a_{r_2}\). It is guaranteed that the length of the subarray \(r_1-l_1+1\) equals \(r_2-l_2+1\).
• 5 l_1 r_1 l_2 r_2: Swap the two subarrays \(a_{l_1}, \dots, a_{r_1}\) and \(a_{l_2}, \dots, a_{r_2}\). The two segments have equal lengths.
• 6 l r: Reverse the subarray \(a_l, a_{l+1}, \dots, a_r\).

After processing all operations, output the final state of the array (all values modulo \(10^9+7\)).

Note: For every operation, for each parameter except the first one, the actual value is obtained by computing given_value XOR last, where \(last\) is the answer of the most recent type \(1\) operation (or 0 initially).

inputFormat

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

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\), the initial values of the array.

Each of the following \(q\) lines contains an operation. The first integer of the line is the operation type (an integer between 1 and 6). For each operation, all integers except the first one are given in an encoded form and should be decoded by taking the XOR with \(last\), where \(last\) is defined as above.

It is guaranteed that the operations are valid and that in operations of type 4 and 5, the lengths of the intervals match.

outputFormat

Whenever a type \(1\) operation is encountered, output the answer (sum of the corresponding subarray modulo \(10^9+7\)) on a new line.

After processing all operations, output the final state of the array in one line (\(n\) integers separated by spaces), with each element taken modulo \(10^9+7\).

sample

5 6
1 2 3 4 5
1 1 5
3 14 12 10
1 14 12
2 17 16 20
4 20 23 17 16
6 23 17

15
21
6 6 8 7 7