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