Problem Description

To enhance the counting skills of kindergarten children, Teacher Xiaohu has assigned a family game homework. She asks Xiaohu to use an empty Go board and randomly place some chess pieces (with two colors, black and white) in some squares. If a square and one of its adjacent squares (up, down, left, or right) have chess pieces of the same color, they are considered connected. During this process, Xiaohu is required to continuously count the number of connected blocks.

The following is a $5\times 9$ chessboard, where . represents an empty square, * represents a black chess piece, and @ represents a white chess piece.

There are $4$ connected blocks.

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

Brother Dahou watches and thinks, if the chessboard is $N\times N$ and there are $M$ chess pieces placed, how can this problem be solved 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 the color of the chess piece to be placed (0 for white, 1 for black), the row coordinate, and the column coordinate of the square where the piece is placed.

Output Format

There are $M$ lines in total. The $i$-th line contains an integer indicating the number of connected blocks after placing the $i$-th chess piece.

Sample Input and Output

Sample Input #1

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

Sample Output #1

1 
1 
2 
3 
2

Sample Input #2

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

Sample Output #2

1
2
3
4
1

Notes

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

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

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

见题面 Input 部分

见题面 Output 部分