Garrison 和 Anderson 在一家名为“Adjustment Office”的公司工作。在竞争对手公司，员工们试图改变现实，而在这家公司，他们试图预测未来。

他们拥有一个 $n \times n$ 的大方格棋盘。最初，棋盘上每个单元格 $(x, y)$ 都写着 $x + y$ 的值（$1 \le x, y \le n$）。他们知道未来棋盘上会有两种类型的查询：

• “R $r$” —— 求出第 $r$ 行所有值的总和，输出结果，并将第 $r$ 行的所有值设为零；
• “C $c$” —— 求出第 $c$ 列所有值的总和，输出结果，并将第 $c$ 列的所有值设为零。

他们已经预测了将会出现的查询及其结果。他们需要确保自己正确预测了结果。请通过计算查询结果来帮助他们。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 10^6, 1 \le q \le 10^5$)，分别表示方格的大小和查询的数量。

接下来的 $q$ 行，每行包含一个查询的描述。每个查询要么是 “R $r$” ($1 \le r \le n$)，要么是 “C $c$” ($1 \le c \le n$)。

输出格式

输出文件应包含 $q$ 行。第 $i$ 行应包含一个整数，即第 $i$ 个查询的结果。

样例

输入 1

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

输出 1

12
10
0
5
5
4
0