Sequence Operations Simulation

You are given a sequence \(a_1,a_2,\dots,a_n\) and need to perform \(m\) operations. There are three types of operations:

• Operation 1: Given integers \(l, r, x\), first create a copy \(b\) of the current array \(a\) (i.e. \(b_i=a_i\) for all \(i\)), then update the segment \(a_x, a_{x+1}, \dots, a_{x+(r-l)}\) with the values \(b_l, b_{l+1}, \dots, b_r\) respectively.
• Operation 2: Given integers \(l, r\), update each element \(a_l, a_{l+1}, \dots, a_r\) to \(\lfloor{a_i/2}\rfloor\) (i.e. floor division by 2).
• Operation 3: Given integers \(l, r\), output the sum of the segment \(a_l, a_{l+1}, \dots, a_r\).

The input guarantees that the operations are valid. It is required to simulate the operations in order. For every Operation 3, the sum of the specified segment should be printed in separate lines.

inputFormat

The first line contains two space-separated integers \(n\) and \(m\) \( (1 \leq n, m \leq 10^5) \) --- the length of the sequence and the number of operations respectively.

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\) --- the initial array.

Each of the next \(m\) lines describes an operation. The first integer of each operation is the operation type.

• If the operation type is 1, three integers \(l, r, x\) follow.
• If the operation type is 2, two integers \(l, r\) follow.
• If the operation type is 3, two integers \(l, r\) follow.

outputFormat

For each operation of type 3, print a single line containing the sum of the subarray \(a_l, a_{l+1}, \dots, a_r\) at that moment.

sample

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

15
10