给定一个 $n \times n$ 的棋盘状方格阵列。行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $n$。

初始时，棋盘的颜色分布如下：若 $i+j$ 为奇数，则第 $i$ 行第 $j$ 列的方格为黑色；若 $i+j$ 为偶数，则该方格为白色。

接下来将依次进行 $q$ 次颜色反转操作，每次操作为以下两种之一：

• 行颜色反转：给定行号，反转该行所有方格的颜色。白色方格变为黑色，黑色方格变为白色。
• 列颜色反转：给定列号，反转该列所有方格的颜色。白色方格变为黑色，黑色方格变为白色。

在每次操作后，需要统计棋盘上不同区域的数量。这里，“区域”定义为一组颜色相同且直接或间接相连的方格。若两个方格共享一条边，则称它们直接相连。

输入格式

输入包含一组测试数据，格式如下：

$n \ q$ $operation_1$ $\vdots$ $operation_q$

其中 $n$ 为行数和列数 ($1 \le n \le 5 \times 10^5$)，$q$ 为操作次数 ($1 \le q \le 5 \times 10^5$)。接下来的 $q$ 行表示按顺序进行的操作，每种操作格式如下：

• ROW i：对第 $i$ 行进行“行颜色反转”操作 ($1 \le i \le n$)。
• COLUMN j：对第 $j$ 列进行“列颜色反转”操作 ($1 \le j \le n$)。

输出格式

输出 $q$ 行。第 $k$ 行应包含一个整数，表示第 $k$ 次操作后棋盘上区域的数量。

样例

样例输入 1

3 3
ROW 2
COLUMN 3
ROW 2

样例输出 1

3
2
6

样例输入 2

200000 2
ROW 1
ROW 1

样例输出 2

39999800000
40000000000

图 F.1. 样例输入 1 的示意图