Adjustment Office#7561
Garrison and Anderson are working in a company named "Adjustment Office". In competing companies workers change the reality, in this company they try to predict the future.
They are given a big square board n \times n. Initially in each cell of this board the value of x + y~(1 \le x, y \le n) is written. They know that in the future there will be two types of queries on the board:
"" — sum up all values in row , print the result and set all values in row to zero;
"" — sum up all values in column , print the result and set all values in column to zero.
They have predicted what queries and results there will be. They need to ensure that they have correctly predicted the results. Help them by computing the results of the queries.
The first line contains two integers and q~(1 \le n \le 10^6, 1 \le q \le 10^5) — the size of the square and the number of queries.
Each of the next lines contains the description of the query. Each query is either "R~r"~(1 \le r \le n) or "C~c"~(1 \le c \le n).
Print lines. The -th line shall contain one integer — the result of the -th query.
Пример 1