Description

To improve kindergarten kids’ counting skills, Teacher Xiaohu gave a family game homework. He asked Xiaohu to take an empty Go board and randomly place some pieces (in two colors: black and white) on some cells. If a cell and one of its four neighbors (up, down, left, right) both contain pieces of the same color, then the two cells are considered connected. During this process, Xiaohu must keep counting how many connected components there are in total.

The figure below shows a $5\times 9$ board, where . means an empty cell, * means a black piece, and @ means a white piece.

Then there are $4$ connected components.

.  .  .  .  .  .  .  .  .
.  .  *  *  .  .  @  @  .
.  *  *  @  @  .  @  @  .
.  .  *  @  .  .  *  .  .
.  .  .  .  .  .  .  .  .

Big brother Dahu watched and thought: if the board is $N\times N$ and a total of $M$ pieces are placed, how can we solve this problem using a computer?

Input Format

The first line contains two integers: $N, M$.

The next $M$ lines each contain three integers: $c, x, y$. They represent, in order, the color of the piece to be placed ($0$ means white, $1$ means black), the row coordinate, and the column coordinate of the cell where it is placed.

Output Format

Output $M$ lines in total. The $i$-th line contains one integer, which is the number of connected components of pieces after placing the $i$-th piece.

3 5    
1 1 1  
1 1 2  
0 2 2  
1 3 1  
1 2 1  

1 
1 
2 
3 
2

3 5
1 1 2
1 2 1
1 3 2
1 2 3
1 2 2

1
2
3
4
1

Hint

For $30\%$ of the testdata: $1\le N \le 10$.

For $60\%$ of the testdata: $1\le N\le 100$.

For $100\%$ of the testdata: $1\le N\le 500$, $1\le M \le N \times N$, $0 \le c \le 1$, $1\le x, y \le N$.

Translated by ChatGPT 5