favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

# Data Structures

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 × n. Initially in each cell (x, y) of this board the value of x + y is written (1x, yn). They know that in the future there will be two types of queries on the board:

• “**R r**” - sum up all values in row r, print the result and set all values in row r to zero;
• “**C c**” - sum up all values in column c, print the result and set all values in column c 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.

#### Input

The first line contains two integers n and q (1n`106`, 1q`105`) - the size of the square and the number of queries.

Each of the next q lines contains the description of the query. Each query is either “**R r**” (1rn) or “**C c**” (1cn).

#### Output

Print q lines. The i-th line shall contain one integer - the result of the i-th query.

Time limit 1 second
Memory limit 128 MiB
Input example #1
```3 7
R 2
C 3
R 2
R 1
C 2
C 1
R 3
```
Output example #1
```12
10
0
5
5
4
0
```
Source 2015 ACM NEERC, Semifinals, December 6, Problem A