Time Limit: 2s
Memory Limit: 512MB
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