Happy Children’s Day

Description:

Children’s Day is coming . In this day , children will get a lot of candies . In MAX city , people develop an automatic candy management ( ACM ) system . ACM  can manage N piles of candies . The system can carry out two operations .

( 1 ) I a b c ( 1 <= a <= b <= N , 0 < c <= 100 ) , ACM will add each pile numbered from a to b with c candies .

( 2 ) C a b ( 1<= a <= b <= N ) , ACM will choose the pile ( from a to b ) with the most candies , and give all the candies in that pile to one child . If two or more piles have the most candies , then the pile with smaller id will be chosen .

Given a series of instructions , for each operation C a b , please help the people to find out the number of candies a child can get .

Input:

Input may contain several test data sets .

For each data set , the first line contains tow integers N , M ( 0 < N , M <= 10⁵ ) where N indicates the number of piles , and M indicates the number of operations that follows .

Each of the next M lines describe one operation .

Input will be ended by N=0 , M=0 , which should not be processed .

        NOTE : At the beginning of each data set , all of the N piles have 0 candies .

Output:

For each operation C a b , print the number of candies the child can get in a line .

Sample Input:

5 4
I 1 5 1
C 2 3
I 2 2 4
C 2 3
0 0

Sample Output:

1
4

Note:

本题由旧版NOJ导入，来源：NUPT ACM