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  |
|             |                | s 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 separated 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