Given a zero-indexed array ~a~ of ~N~ integers, perform ~Q~ operations on it.

Operation	Defintion
REPLACE i v	Replace the ~i^\text{th}~ integer with ~v~.
ROTATELEFT i j	Rotate the subarray beginning at ~i~ and ending at ~j~, inclusive, to the left. The ~j^\text{th}~ integer is now the ~i^\text{th}~ integer, the integer at index ~i~ is now the integer at index ~i+1~, et cetera.
ROTATERIGHT i j	Rotate the subarray beginning at ~i~ and ending at ~j~, inclusive, to the right. The integer at index ~i~ is now the integer at index ~j~, the integer at index ~i+1~ is now the integer at index ~i~, et cetera.
FLIP i j	Flip the subarray ~[i, j]~. The integer at index ~i~ is swapped with the integer at index ~j~, ~i+1~ with ~j-1~, et cetera.
RANGEUPDATE i j v	Set all the elements between ~i~ and ~j~, inclusive, to the integer ~v~.
MAX i j v	For all elements between ~i~ and ~j~, if the element has a value less than ~v~, set it to ~v~. Otherwise, increment the element by ~v~.
SUM i j	Sum up the elements between ~i~ and ~j~, inclusive. Output this value.
CONDITIONALMINSUM i j k	Sum up the elements between ~i~ and ~j~, inclusive, that have a value less than or equal to ~k~. If there are no elements, the answer is 0. Output this value.
COUNT i j k	Count the number of elements between ~i~ and ~j~, inclusive, that have a value of ~k~. Output this value.
MAXSUM	Find the maximum sum of any subarray in the array. Note that the subarray must not be empty. A subarray of an array is a continuous section of the array. Output this value.

~0 \le i \le j \le N~, ~-2 \times 10^9 \le k \le 2 \times 10^9~, and ~-2000 \le v \le 2000~.

Input Specification

The first line will contain two integers ~N, Q~ ~(1 \le N, Q \le 1000)~.

The next line will contain ~N~ integers, ~a_i\ (-2000 \le a_i \le 2000)~, the initial values of the array.

The next ~Q~ lines will contain an operation as defined above.

Output Specification

For each operation that outputs a value, print it on a new line.

Subtasks

Subtask 1 [50%]

There will be no ROTATELEFT, ROTATERIGHT, FLIP, COUNT, or MAXSUM operations.

Subtask 2 [45%]

There wlll be no MAXSUM operations.

Subtask 3 [5%]

No further constraints.

Sample Input

4 6
1 2 3 4
SUM 0 3
REPLACE 1 -1
CONDITIONALMINSUM 0 2 1
RANGEUPDATE 2 3 1
MAX 0 3 1
SUM 0 3

Sample Output

10
0
7