Dynamic Array Operations

You are given an array \(A\) of length \(n\) with 1-indexed positions. You need to process \(m\) operations on the array. The operations are of the following four types:

• Type 1: Append an integer \(x\) to the end of the array \(A\).
• Type 2: Output the sum \(\sum_{i=l}^{r} A_i\) where \(l\) and \(r\) denote the indices (1-indexed).
• Type 3: For every \(i\), update \(A_i = A_i \oplus x\) where \(\oplus\) denotes the bitwise XOR operation.
• Type 4: Sort the array \(A\) in non-decreasing order.

Process all \(m\) operations in order. For each operation of type 2, output the corresponding sum on a new line.

inputFormat

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

The second line contains \(n\) space-separated integers representing the initial elements of the array \(A\).

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

• If the operation is type 1: 1 x
• If the operation is type 2: 2 l r
• If the operation is type 3: 3 x
• If the operation is type 4: 4

outputFormat

For each operation of type 2, output the sum \(\sum_{i=l}^{r} A_i\) on a separate line.

sample

5 5
1 2 3 4 5
2 1 3
1 10
3 1
4
2 2 6

6
20