Sequence Operations

Given a sequence of integers and a series of operations, you need to maintain the sequence by performing the following operations:

• INSERT x n a₁ a₂ ... a_n: Insert \(n\) numbers \(a_1, a_2, \dots, a_n\) immediately after the \(x\)-th element of the sequence.
• DELETE x n: Delete \(n\) numbers from the sequence, starting at the \(x\)-th element.
• REVERSE x n: Reverse the subarray of \(n\) numbers starting at the \(x\)-th element.
• MAKE-SAME x n t: Change the \(n\) numbers starting from the \(x\)-th element to the value \(t\).
• GET-SUM x n: Print the sum of the \(n\) numbers starting at the \(x\)-th element.
• GET x: Print the value of the \(x\)-th element.
• MAX-SUM x n: Print the maximum contiguous subarray sum within the subarray of \(n\) numbers starting from the \(x\)-th element. (If all numbers are negative, output the largest number.)

All indices in the operations are 1-indexed.

inputFormat

The first line contains two integers (n) and (m), representing the initial length of the sequence and the number of operations, respectively. The second line contains (n) integers that form the initial sequence. Each of the following (m) lines contains one operation in one of the formats described above.

outputFormat

For each operation that requires an output (i.e. GET, GET-SUM, and MAX-SUM), print the corresponding result on a new line.

sample

5 8
1 2 3 4 5
GET-SUM 2 3
INSERT 3 2 10 11
GET 4
MAKE-SAME 1 3 0
GET-SUM 1 7
REVERSE 4 3
GET 5
MAX-SUM 1 7

9
10
30
11
30