题目描述

为了增强幼儿园小朋友的数数能力，小虎的老师给了一个家庭游戏作业。他让小虎拿一块空的围棋盘，随机地在一些方格中放些棋子（有黑白两种颜色），如果一个方格和它的上、下、左、右四个方格之一都有相同颜色的棋子，则认为两格子是相连通的。这期间，要求小虎不断统计共有多少个连通块。

如下图是一个 $5×9$ 的棋盘，其中 “.” 表示空格，“*” 表示黑棋子，“@” 表示白棋子。则有 $4$ 块连通的棋子块。

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

哥哥大虎在一边看一边想，如果棋盘是 $N \times N$ 的，共放了 $M$ 个棋子，如何用计算机解决这个问题呢？

输入格式

第 1 行两个整数： $N$，$M$( $1 \le N \le 500$，$1 \le M \le N \times N$)。

接下来有 $M$ 行，，每行三个正整数：$C，X，Y$( $0 \le C \le 1$，$1 \le X，Y \le N$ )，分别表示依次放入棋子的颜色（ $0$ 表示白色，$1$ 表示黑色）、要放入格子的横坐标和格子的纵坐标。

输出格式

共 $M$ 行。第 $i$ 行一个整数，表示放入第 $i$ 个棋子后，当前有多少个棋子连通块。

样例

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

1
1
2
3
2