Description

加里森和安德森在一家名为“Adjustment Office”的公司工作。在竞争公司中，员工改变现实，而在这家公司中，他们尝试预测未来。

他们得到一个 $n \times n$ 的大方板。最初在这个方板的每个单元格 $(x, y)$ 中写着 $x + y$ 的值（$1 \leq x, y \leq n$）。他们知道在未来将会有两种类型的查询：

• “R $r$”——计算第 $r$ 行的所有值之和，打印结果并将第 $r$ 行的所有值设为零；
• “C $c$”——计算第 $c$ 列的所有值之和，打印结果并将第 $c$ 列的所有值设为零。

他们已经预测了将会有哪些查询和结果。他们需要确保他们正确预测了结果。请帮助他们计算查询的结果。

Input Format

输入的第一行包含两个整数 $n$ 和 $q$（$1 \leq n \leq 10^6$，$1 \leq q \leq 10^5$）——方板的大小和查询的数量。

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

Output Format

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

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

12
10
0
5
5
4
0

Hint

时间限制：1 秒，内存限制：256 MB。

题面翻译由 ChatGPT-4o 提供。