Sequence Maintenance

You are given an initial sequence of integers and a series of operations to perform on the sequence. The operations are defined as follows. All positions in the operations (except for the INSERT operation) are 1-indexed. For the INSERT operation, if posi is 0, insert at the beginning; otherwise, insert after the posi-th element.

No.	Name	Format	Description
1	INSERT	$$\operatorname{INSERT}\ posi\ tot\ c_1\ c_2 \cdots c_{tot}$$	After the posi-th number in the current sequence (if posi = 0, insert at the beginning), insert tot numbers: c_1, c_2, \ldots, c_{tot}.
2	DELETE	$$\operatorname{DELETE}\ posi\ tot$$	Delete tot consecutive numbers starting from the posi-th number of the current sequence.
3	MAKE-SAME	$$\operatorname{MAKE\text{-}SAME}\ posi\ tot\ c$$	Change tot consecutive numbers starting from the posi-th number to the value c.
4	REVERSE	$$\operatorname{REVERSE}\ posi\ tot$$	Reverse the order of tot consecutive numbers starting from the posi-th number.
5	GET-SUM	$$\operatorname{GET\text{-}SUM}\ posi\ tot$$	Compute and output the sum of tot consecutive numbers starting from the posi-th number.
6	MAX-SUM	$$\operatorname{MAX\text{-}SUM}$$	Find and output the maximum subarray sum in the current sequence. If the sequence is empty, output 0.

Input Format:

The first line contains two integers n and m, which represent the initial number of elements in the sequence and the number of operations, respectively.

The second line contains n integers representing the initial sequence.

The following m lines each contain one operation in one of the formats described above.

Output Format:

For each GET-SUM and MAX-SUM operation, output the result on a new line.

inputFormat

The first line contains two integers n and m (initial sequence length and number of operations).

The second line contains n integers representing the initial sequence.

Each of the next m lines contains one operation, which can be one of the following:

• INSERT posi tot c1 c2 ... c_tot
• DELETE posi tot
• MAKE-SAME posi tot c
• REVERSE posi tot
• GET-SUM posi tot
• MAX-SUM

outputFormat

For every GET-SUM and MAX-SUM operation, output the result on a separate line.

sample

5 5
1 2 3 4 5
GET-SUM 2 3
INSERT 3 2 10 20
GET-SUM 4 3
REVERSE 2 4
MAX-SUM

9
34
45

</p>