거대한 체스판에서의 색 반전

사각형 칸들이 체스판처럼 $n$개의 가로줄(행)과 $n$개의 세로줄(열)로 놓여 있다. 행은 위에서 아래로 $1$번부터 $n$번까지, 열은 왼쪽에서 오른쪽으로 $1$번부터 $n$번까지 번호가 매겨져 있다.

처음에 칸들은 체스판처럼 칠해져 있다. 행 $i$, 열 $j$의 칸은 $i + j$가 홀수이면 검은색, 짝수이면 흰색이다.

색 반전 연산이 차례로 수행된다. 연산은 다음 두 가지 중 하나이다.

행의 색 반전: 행 번호가 주어지면 그 행에 있는 모든 칸의 색을 반전한다. 흰 칸은 검은색이 되고, 검은 칸은 흰색이 된다.

열의 색 반전: 열 번호가 주어지면 그 열에 있는 모든 칸의 색을 반전한다. 흰 칸은 검은색이 되고, 검은 칸은 흰색이 된다.

각 연산을 수행한 뒤 영역의 개수를 센다. 영역은 같은 색의 칸들이 직접 또는 간접적으로 연결된 집합이다. 두 칸이 변을 공유하면 직접 연결된 것으로 본다.

입력은 다음 형식의 테스트 케이스 하나로 이루어진다.

$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$번째 연산을 수행한 뒤의 영역 개수를 출력한다.

그림 F.1. 첫 번째 입력 예시의 설명 그림.