## SEQ2 - Another Sequence Problem

no tags

You are to write a program to perform some operations on a given sequence.These operations are listed below:

```---------------------------------------------------------------------------------------------
| Name        | Input format   |              function                                      |
---------------------------------------------------------------------------------------------
| Modify      | MAKE-SAME i t c| Modify all the t numbers from the ith number(included) to  |
|             |                | number c.                                                  |
---------------------------------------------------------------------------------------------
| Insert      | INSERT i t s   | Insert t numbers after the ith number.s is a sequence of t |
|             |                | numbers which should be inserted one-to-one.If i=0,you     |
|             |                | should insert s in the first of the sequence.              |
---------------------------------------------------------------------------------------------
| Delete      | DELETE i t     | Delete t numbers after the ith number(included).           |
---------------------------------------------------------------------------------------------
| Reverse     | REVERSE i t    | Reverse t numbers after the ith number(included).          |
---------------------------------------------------------------------------------------------
| Get sum     | GET-SUM i t    | Output the sum of t numbers after the ith number(included).|
---------------------------------------------------------------------------------------------
| Get maximum | MAX-SUM        | Output the maximum partial sum in the sequence now.        |
| partial sum |                |                                                            |
---------------------------------------------------------------------------------------------
```

See the example.

### Input

The very first line contains a single integer T(T<=4), the number of test cases.T blocks follow.

For each test case:

The first line contains two integers n and m(m<=20000), the number of numbers in the sequence in the beginning and the number of operations.

The second line contains n integers seperated by spaces, the sequence in the beginning.

Next m lines, each contains an operation listed above.

You can assume that for each test case:

• No invalid operation is in the input.
• Number of numbers in the sequence is no more than 500000 and not less than 1 at any time.
• All the numbers in the sequence is in range[-1000,1000] at any time.
• The total number of numbers inserted will be not more than 4,000,000.The input is no more than 20MB.

### Output

For each Get sum and Get maximum partial sum operation,you should write the answer to the output,one per line.

### Example

```Input:
1
9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM

Output:
-1
10
1
10

Hints:
After the 3rd op., the sequence is
2 -6 3 5 1 -5 -3 6 -5 7 2 3

After the 4th op., the sequence is
2 -6 3 5 1 -5 -3 6 -5 7 2

After the 5th op., the sequence is
2 -6 2 2 2 -5 -3 6 -5 7 2

After the 6th op., the sequence is
2 -6 6 -3 -5 2 2 2 -5 7 2

```
Warning: enormous Input/Output data, be careful with certain languages

hide comments Mark Gordon: 2014-06-18 07:21:59 Apparently MAX-SUM actually wants you to output the maximum sum of any non-empty contiguous subsequence of the array. This is not at all clear from the problem statement. Liang Zhao: 2013-02-25 14:32:50 If all the numbers are negative, is the MAX-SUM 0 or the biggest one? @[Trichromatic] XilinX \$!:D: 2012-09-28 05:08:47 can u xplain how to calculate the max. partial sum Fotile: 2011-11-26 12:05:19 There are queries like "GET-SUM 8 0". Take care

 Added by: Fudan University Problem Setters Date: 2007-04-01 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: C99 ERL JS-RHINO Resource: Chinese National Olympiad in Informatics 2005,Day 1; translated by lcosvse