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:

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