题目描述

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

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

.........

..**..@..

.**@@.@@.

..*@..*..

.........

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

输入要求

第1行两个整数：N，M（1≤N≤500，1≤M≤N×N）。

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

输出要求

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

In order to enhance the ability of kindergarten children count, Tiger s teacher gave the job of a family game. He let the Tigers get an empty chess set, randomly put some pawn in some grid (black or white), if a box and it s one of the down, left, and right box have pawn of the same color, the two grid connect. During this period, the Tigers continue to Statistics Total number of connected blocks.

The following figure is a 5 × 9 board, where "space,"* "represents the black pawn," @ ", said the white pawn. There are four connected piece.

.........

..** .. @ ..

.** @ @ @ @.

..* @ ..* ..

.........

Brothers and Big Tiger, he is thinking while watching, if the board is the N × N, let M a pawn how to use the computer to solve this problem?

Input requirements

1 lines of two integers: N, M, (1 ≤ N ≤ 500,1 ≤ M ≤ N × N).

Next M lines, each line of three positive integers: C and the X, Y (0 ≤ C ≤ 1,1 ≤ X, Y, ≤ N), respectively, turn into the color of the pawn (0 white