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 may contain several test data sets .
For each data set , the first line contains tow integers N , M ( 0 < N , M <= 105 ) 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 .
For each operation C a b , print the number of candies the child can get in a line .
I 1 5 1
C 2 3
I 2 2 4
C 2 3