Board Query Prediction

Garrison and Anderson work in a company called “Adjustment Office” and they predict the future. They are given a big square board of size \(n \times n\). Initially, each cell \((x, y)\) where \(1 \le x, y \le n\) contains the value \(x+y\) (written in \(\LaTeX\)).

There will be two types of queries performed on the board in the future:

• R r: Sum all the values in row \(r\), print the result, and set all values in row \(r\) to zero.
• C c: Sum all the values in column \(c\), print the result, and set all values in column \(c\) to zero.

After each query, the affected row or column becomes zero for subsequent queries. Given the queries in order, compute the results of each query.

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \le n, q \le 10^5)\) representing the size of the board and the number of queries, respectively.

Each of the next \(q\) lines contains a query in one of the following formats:

• R r (\(1 \le r \le n\)): Query on row \(r\).
• C c (\(1 \le c \le n\)): Query on column \(c\).

outputFormat

For each query, output a single line containing the result of that query.

sample

3 4
R 2
C 3
R 2
C 1

12
10
0
6