SEQ2  Another Sequence Problem
You are to write a program to perform some operations on a given sequence.These operations are listed below:
  Name  Input format  function    Modify  MAKESAME 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 onetoone.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  GETSUM i t  Output the sum of t numbers after the ith number(included).   Get maximum  MAXSUM  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 GETSUM 5 4 MAXSUM INSERT 8 3 5 7 2 DELETE 12 1 MAKESAME 3 3 2 REVERSE 3 6 GETSUM 5 4 MAXSUM Output: 1 10 1 10 Hints:Warning: enormous Input/Output data, be careful with certain languagesAfter the 3rd op., the sequence is
2 6 3 5 1 5 3 6 5 7 2 3After the 4th op., the sequence is
2 6 3 5 1 5 3 6 5 7 2After the 5th op., the sequence is
2 6 2 2 2 5 3 6 5 7 2After the 6th op., the sequence is
2 6 6 3 5 2 2 2 5 7 2
hide comments
Mark Gordon:
20140618 07:21:59
Apparently MAXSUM actually wants you to output the maximum sum of any nonempty contiguous subsequence of the array. This is not at all clear from the problem statement. 

Liang Zhao:
20130225 14:32:50
If all the numbers are negative, is the MAXSUM 0 or the biggest one?


$!:D:
20120928 05:08:47
can u xplain how to calculate the max. partial sum 

Fotile:
20111126 12:05:19
There are queries like "GETSUM 8 0". Take care 
Added by:  Fudan University Problem Setters 
Date:  20070401 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: C99 ERL JSRHINO 
Resource:  Chinese National Olympiad in Informatics 2005,Day 1; translated by lcosvse 