Description

你被给予一个按棋盘状排列的方格集合，有 $n$ 行和 $n$ 列。行从上到下编号为 $1$ 到 $n$，列从左到右也编号为 $1$ 到 $n$。

初始时，方格像国际象棋棋盘一样着色：如果 $i + j$ 为奇数，则位于第 $i$ 行第 $j$ 列的方格为黑色；如果为偶数，则为白色。

随后依次进行颜色反转操作，每次操作是以下两种之一：

反转某行的颜色：给定一个行号，反转指定行中所有方格的颜色。该行中的白色方格变为黑色，黑色方格变为白色。

反转某列的颜色：给定一个列号，反转指定列中所有方格的颜色。该列中的白色方格变为黑色，黑色方格变为白色。

需要在每次操作后统计不同的 区域 数量。这里，区域是指由相同颜色、直接或间接相连的方格组成的集合。当两个方格共享一条边时，称它们直接相连。

Input Format

输入由单个测试用例组成，格式如下。

$$\begin{aligned} &n\ q \\ &operation_1 \\ &\vdots \\ &operation_q \end{aligned}$$

整数 $n$ 是行数和列数 ($1 \leq n \leq 5 \times 10^5$)。整数 $q$ 是操作的数量 ($1 \leq q \leq 5 \times 10^5$)。接下来的 $q$ 行按顺序表示要执行的操作。每行是以下两种形式之一：

• ROW $i$：表示对第 $i$ 行 ($1 \leq i \leq n$) 执行“反转某行的颜色”操作。
• COLUMN $j$：表示对第 $j$ 列 ($1 \leq j \leq n$) 执行“反转某列的颜色”操作。

Output Format

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

3 3
ROW 2
COLUMN 3
ROW 2

3
2
6

200000 2
ROW 1
ROW 1

39999800000
40000000000

Hint

:::align{center}

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