시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 0 0 0 0.000%

문제

Please write a program that maintains a sequence, supporting the following 6 operations:

Operation Input Format Description
1. Insert INSERT posi tot c1 c2 … ctot After the posi-th number in the current sequence, insert a total of tot numbers: c1c2, …, ctot. Insertion to the beginning of the sequence will have posi equal to 0.
2. Delete DELETE posi tot Starting at the posi-th number in the current sequence, delete a total of tot consecutive numbers.
3. Modify MAKE-SAME posi tot c Starting at the posi-th number in the current sequence, change all the values of tot consecutive numbers to c.
4. Reverse REVERSE posi tot Starting at the posi-th number in the current sequence, reverse the order of tot consecutive numbers.
5. Get Sum GET-SUM posi tot Starting at the posi-th number in the current sequence, output the sum of tot consecutive numbers.
6. Max Sum MAX-SUM Output the largest sum of any (non-empty) consecutive subsequence of the current sequence.

입력

The first line of input contains two integers N and M, where N is the initial length of the sequence and M is the number of operations.

The second line of input contains N integers, describing the initial sequence.

For the next M lines, each line will contain a command in one of the formats described above.

출력

For each GET-SUM or MAX-SUM operation in the input, output the result of the query on a separate line.

제한

  • You may assume that at any given time, the sequence will contain at least 1 number.
  • The data in the input is guaranteed to be valid, and will always refer to existing positions in the sequence.
  • The sequence may contain up to 500 000 numbers at any given moment.
  • The value of any number in the sequence will be in the range [-1000, 1000].
  • M ≤ 20 000
  • The sum of all inserted values will not exceed 4 000 000.
  • The input will not exceed 20MB.

예제 입력 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

예제 출력 1

-1
10
1
10