Easy Problem

Time Limit : 2 Second

Memory Limit : 512 MB

Submission: 55

Solved: 4

Description

These days, Keqiang was interested in some digital games. He asked his deskmate, Jinping, to play the game he came up yesterday together. 


There is a square board with n * n grid. The initial value of each cell (x, y) is x + y (1 <= x, y <= n). Then Keqiang will ask Jinping m questions follow the format below.


R r means summing up all values in the row r, print the result and set all values in row r to 0


C c means summing up all values in column c, print the result and set all values in column c to 0


Jinping thinks it’s too difficult to calculate the result, Could you help him?

Input

The first line complains two integers n and q (1 ≤ n ≤ 10^6 , 1 ≤ q ≤ 10^5)  - the size of board and the number of questions


Each of the next m lines contains the description of the question. The format is either “R r” (1 <= r <= n) or “C c” (1 <= c <= n)

Output

The output should contains m lines, the i-th line is one integer shows the result of i-th question.

sample input
3 7
R 2
C 3
R 2
R 1
C 2
C 1
R 3
sample output
12
10
0
5
5
4
0
hint
source
© 2015 HUST ACMICPC TEAM. All Right Reserved.