After another disappointing season, the Toronto Maple Leafs have just fired their general manager, Kyle Dubas!

They are now looking for a new general manager and have compiled a list of ~N~ potential candidates.

However, as the NHL entry draft is only a month away, the Leafs don't have time to individually interview all ~N~ candidates. Thus, they will conduct interviews in batches, and change the scores of the candidates that stand out (each candidate starts with a score of ~0~).

For each interview, the Leafs' president, Brandon Shanahan, wants to know the sum of all candidates' scores, and will also give you several candidate scores to change.

Shanahan will give you ~M~ tasks in total, where each task is formatted as either:

• C i s Increase the ~i~-th candidate's score by ~s~.
• S i j Output the sum of the candidates' scores in the range ~[i, j]~ (inclusive).

Constraints

Subtask 1 [50%]

~1 \le N \le 1000~

~1 \le M \le 5000~

~1 \le s \le 5000~

Subtask 2 [50%]

~1 \le N \le 10^5~

~1 \le M \le 10^6~

~1 \le s \le 10^6~

Input Specification

The first line of input will contain two integers, ~N~ and ~M~.

The next ~M~ will each contain a task in the format described above.

Output Specification

For each operation of type S i j, output the sum of the candidates' scores in the range ~[i, j]~ (inclusive).

At the end of the ~M~ tasks, output the index of the candidate with the highest score. If there are multiple, output the lowest index.

Sample Input

5 10
C 3 5
C 2 7
S 1 3
C 1 2
C 3 3
S 1 4
C 5 1
S 3 5
C 4 2
S 1 5

Sample Output

12
17
9
20
3

Sample Explanation

The first ~4~ lines of output contain the answers to the ~4~ tasks in the form S i j. The last line of output contains the index of the candidate with the highest score.