CONANGSS - Help Conan 8 !! Hurry up !!

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{ap+ap+1+...+aq | 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


Added by:ConanKudo
Date:2008-07-15
Time limit:0.100s-6.734s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Own

hide comments
2012-02-07 05:54:07 Fish
I added
if (l <= 0 || r > n) exit(1);
in my code, and I received a RE(NZEC), perhaps there are something wrong with the data?
2009-08-08 15:55:38 [Trichromatic] XilinX
Needn't use any data structures. O(1) for each update and O(m) for each query will lead to Accepted.

Edit: seems there's a rejudge. Many "Accepted" solutions (mine included) don't work now.

Last edit: 2009-07-03 03:53:18
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.