Maintain a sequence of numbers and support the following 6 operations: (Note: the underscore _ in the format column represents a space in the actual input file)
| Operation ID | Format in Input File | Description |
|---|---|---|
| 1. Insert | INSERT_posi_tot_c1_c2_..._ctot |
Insert tot numbers $c_1, c_2, \dots, c_{tot}$ after the posi-th number in the current sequence; if inserting at the beginning of the sequence, posi is 0 |
| 2. Delete | DELETE_posi_tot |
Delete tot consecutive numbers starting from the posi-th number in the current sequence |
| 3. Modify | MAKE-SAME_posi_tot_c |
Change tot consecutive numbers starting from the posi-th number in the current sequence to c |
| 4. Reverse | REVERSE_posi_tot |
Extract tot numbers starting from the posi-th number in the current sequence, reverse them, and put them back in their original position |
| 5. Sum | GET-SUM_posi_tot |
Calculate and output the sum of tot numbers starting from the posi-th number in the current sequence |
| 6. Max Subsequence Sum | MAX-SUM |
Find and output the maximum sum of a contiguous subsequence in the current sequence |
Input
The first line of the input file contains two numbers $N$ and $M$, where $N$ represents the number of elements in the initial sequence, and $M$ represents the number of operations to perform. The second line contains $N$ numbers, describing the initial sequence. The following $M$ lines each contain one command; see the table in the description for the format.
Output
For the GET-SUM and MAX-SUM operations in the input data, print the results to the output file sequentially, with each answer (number) on a new line.
Examples
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
-1 10 1 10
Note
Initially, the sequence is: 2 -6 3 5 1 -5 -3 6 3
Executing GET-SUM 5 4 calculates the sum of 4 numbers starting from the 5th number: 1 + (-5) + (-3) + 6 = -1.
Executing MAX-SUM finds the maximum contiguous subsequence sum, which is 3 + 5 + 1 + (-5) + (-3) + 6 + 3 = 10.
Executing INSERT 8 3 -5 7 2 inserts -5, 7, 2 after the 8th number:
2 -6 3 5 1 -5 -3 6 -5 7 2 3
Executing DELETE 12 1 deletes the 12th number:
2 -6 3 5 1 -5 -3 6 -5 7 2
Executing MAKE-SAME 3 3 2 changes 3 numbers starting from the 3rd number to 2:
2 -6 2 2 2 -5 -3 6 -5 7 2
Executing REVERSE 3 6 reverses the 6 numbers starting from the 3rd number (2 2 2 -5 -3 6 becomes 6 -3 -5 2 2 2):
2 -6 6 -3 -5 2 2 2 -5 7 2
Finally, executing GET-SUM 5 4 and MAX-SUM yields 1 and 10.
Scoring
This problem features partial scoring. For each test case:
If your program can print the answers for GET-SUM operations in the correct positions in the output file, you will receive 60% of the points for that test case.
If your program can print the answers for MAX-SUM operations in the correct positions in the output file, you will receive 40% of the points for that test case.
The scores from the two conditions above are additive; if your program correctly outputs all answers for both GET-SUM and MAX-SUM operations, you will receive 100% of the points for that test case.
Note: If your program can only correctly handle one type of operation, ensure that you print the results in the correct positions in the output file—that is, you must leave the corresponding lines for the other operation, otherwise we do not guarantee correct scoring.
Constraints
You may assume that at any time, there is at least 1 number in the sequence. The input data is guaranteed to be valid, meaning the specified positions always exist in the sequence. In 50% of the data, the sequence contains at most 30,000 numbers at any time. In 100% of the data, the sequence contains at most 500,000 numbers at any time. In 100% of the data, every number in the sequence is within $[-1000, 1000]$ at any time. In 100% of the data, $M \le 20,000$, the total number of inserted elements does not exceed 4,000,000, and the input file size does not exceed 20 MBytes.