Settlement Office

Garison and Andreson work at a settlement office and want to predict the future. They are given a large $n \times n$ square grid. At the start the element at $(x, y)$ holds $x + y$ ($1 \le x, y \le n$).

Two kinds of queries arrive.

• R r: print the sum of every value in row $r$, then set all of row $r$ to 0.
• C c: print the sum of every value in column $c$, then set all of column $c$ to 0.

Write a program that reports the result of each query in order.

The first line has the grid size $n$ and the number of queries $q$ ($1 \le n \le 10^6$, $1 \le q \le 10^5$).

Each of the next $q$ lines has one query, either R r ($1 \le r \le n$) or C c ($1 \le c \le n$).

Print the result of the $i$-th query on the $i$-th line ($1 \le i \le q$).