Color Inversion on a Huge Chessboard

A set of square cells is arranged in a chessboard-like pattern with $n$ horizontal rows and $n$ vertical columns. Rows are numbered $1$ through $n$ from top to bottom, and columns are numbered $1$ through $n$ from left to right.

Initially, the cells are colored like a chessboard. The cell in row $i$ and column $j$ is black if $i + j$ is odd and white if $i + j$ is even.

Color-inversion operations are applied one after another. Each operation is one of the following two.

Invert colors of a row: Given a row number, invert the colors of all cells in that row. White cells in the row become black, and black cells become white.

Invert colors of a column: Given a column number, invert the colors of all cells in that column. White cells in the column become black, and black cells become white.

After each operation, count the number of areas. An area is a group of cells of the same color that are directly or indirectly connected. Two cells are directly connected when they share an edge.

The input consists of a single test case in the following format.

$n$ $q$

$operation\_1$

$\vdots$

$operation\_q$

The integer $n$ is the number of rows and columns ($1 \le n \le 5 \times 10^5$). The integer $q$ is the number of operations ($1 \le q \le 5 \times 10^5$). The following $q$ lines give the operations in order. Each line has one of the following forms.

• ROW $i$: invert the colors of row $i$ ($1 \le i \le n$).
• COLUMN $j$: invert the colors of column $j$ ($1 \le j \le n$).

Output $q$ lines. The $k$-th line contains the number of areas after the $k$-th operation.

Figure F.1. Illustration of the first sample input.