题目描述

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

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

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

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

输入格式

第一行两个整数：N , M

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

数据范围

30% 数据：1 <= N <= 10

60% 数据：1 <= N <= 100

100% 数据：1 <= N <= 500 , 1 <= M <= N*N。

输出格式

共 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

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

1
2
3
4
1