问题描述

具体描述见教材p186： 为了增强幼儿园小朋友的数数能力，小虎的老师给了一个家庭游戏作业。他让小虎拿一块空的围棋盘，随机地在一些方格中放些棋子(有黑白两种颜色)，如果一个方格和它的上、下、左、右四个方格之一都有相同颜色的棋子，则认为两格子是相连通的。这期间，要求小虎不断统计共有多少个连通块。 如图8-3-5(右文本框中)示是一个5×9的棋盘，其中“.”表示空格，“*”表示黑棋子，“@”表示白棋子。则有4块连通的棋子块。

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

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

格式

输入

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

输出

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

样例

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

限制

1s, 64MB.