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?

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)

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

3 7
R 2
C 3
R 2
R 1
C 2
C 1
R 3

12
10
0
5
5
4
0