# Data structures contest - high level

# Adjustment Office

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 (**1** ≤ **x**, **y** ≤ **n**). 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** (**1** ≤ **n** ≤ `10`

, ^{6}**1** ≤ **q** ≤ `10`

) - the size of the square and the number of queries.^{5}

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

#### Output

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

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

12 10 0 5 5 4 0