Colorful Chessboard

You are given an (n \times n) chessboard with cells colored in an alternating pattern. Initially, the board is colored in a checkerboard pattern: for each cell ((i, j)) (with 1-indexed rows and columns), the cell is white if ((i+j)) is even and black if ((i+j)) is odd. In other words, the first row has white cells at positions (1,3,5,\dots) and black cells at positions (2,4,6,\dots); the second row is the reverse: white at positions (2,4,6,\dots) and black at positions (1,3,5,\dots), and so on.

You will perform (q) operations. In each operation, you choose either a row or a column and flip the colors of all its cells (i.e. white cells become black and black cells become white). After each operation, you are to determine the number of connected regions in the board that are uniformly colored (either all black or all white). Two cells are considered connected if they share a common side (i.e. four-directionally connected).

Note that if you denote by (R[i]) (resp. (C[j])) the number of flips (mod 2) applied to row (i) (resp. column (j)), then the color of cell ((i,j)) becomes [ \text{color}(i,j) = \big((i+j) + R[i] + C[j]\big) \bmod 2. ]

Observe that adjacent cells in the same row are connected if and only if the corresponding columns have the same effective parity, and similarly for columns. In fact, if we define:

[ A[i] = (i + R[i]) \bmod 2 \quad\text{and}\quad B[j] = (j + C[j]) \bmod 2, ]

then the color of cell ((i,j)) equals (A[i] + B[j] \bmod 2). A vertical edge (between (i) and (i+1)) remains uncut if (A[i] = A[i+1]), and a horizontal edge (between (j) and (j+1)) remains uncut if (B[j] = B[j+1]). Therefore, the board is partitioned into connected regions which are exactly the Cartesian product of the contiguous segments in rows and columns. If (r_{group}) denotes the number of contiguous segments (groups) in the rows and (c_{group}) denotes that in the columns then the answer is

[ \text{Answer} = r_{group} \times c_{group}, ]

where

[ r_{group} = 1 + #{i \in [1, n-1] : A[i] \neq A[i+1]} \quad\text{and}\quad c_{group} = 1 + #{j \in [1, n-1] : B[j] \neq B[j+1]}. ]

Your task is to process the (q) operations and output the number of connected regions after each operation.

inputFormat

The first line contains two integers (n) and (q) (the dimensions of the chessboard and the number of operations). Each of the following (q) lines contains an operation in the format:

op pos

Here, op is a character that is either 'R' (indicating a row flip) or 'C' (indicating a column flip), and pos (1-indexed) specifies the row or column to flip.

outputFormat

Output (q) lines. The (i)-th line should contain a single integer representing the total number of connected regions (of uniform color) after the (i)-th operation.

sample

3 3
R 1
C 2
R 3

6
2
1

</p>