Counting Haybales

Input

The first line contains two positive integers n~(1 \le n \le 2 \cdot 10^5) and q~(1 \le q \le 10^5).

The next line contains $n$ nonnegative integers, each at most 10^5, indicating the initial number of haybales in each field.

Each of the next $q$ lines contains a single uppercase letter, either $M$, $P$, or $S$, followed by either two positive integers $a$ and $b$ (1 \le a \le b \le n), or three positive integers $a$, $b$, and $c$ (1 \le a \le b \le n, 1 \le c \le 10^5). There will be three positive integers if and only if the uppercase letter is $P$.

If the letter is $M$, print the minimum number of haybales in the interval of fields from $a\dots b$.

If the letter is $P$, add $c$ new haybales to each field in the interval of fields from $a\dots b$.

If the letter is $S$, print the total number of haybales in the interval of fields from $a\dots b$.

Output

For each $M$ or $S$ operation in FJ's instructions, output one line containing the answer to that operation.

Examples