Given a sequence of n numbers (initially all is equal to 0) and m queries of two kinds:

U i j v increase all numbers from position i to position j by v (v may be negative)

Q i j query max{a_p+a_p+1+...+a_q | i <= p <= q <= j} as in problem GSS1 and GSS3

You have to process these queries and print out the answer for each query of type Q.

The time limit for this problem is 2s.

Input

- First line: n, m (1 <= n <= 20000, 1 <= m <= 20000)

- In each line of the next m lines there is a query of one of the two forms above.

Output

For each query of type Q, print out the corresponding answer.

Example

Input:
4 2
U 1 3 2
Q 1 4
Output:
6