ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5354: 帕夏和像素

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：3 通过：3
提交提交记录统计Web Board

题目描述

  帕夏喜欢他的手机，也喜欢把头发梳起来……但现在头发已经无关紧要了。

  帕夏在手机上安装了一款新游戏。游戏的目标如下。有一个矩形场，由n行组成，每行有m个像素。最初，所有像素都是白色的。在一个动作中，帕夏可以选择任何像素并将其涂成黑色。特别是，他可以选择已经是黑色的像素，然后在男孩移动后，像素不会改变，也就是说，它保持黑色。当由黑色像素组成的2×2正方形形成时，帕夏输掉了比赛。

  帕夏已经制定了一个k次移动的计划，他将根据该计划绘制像素。他的计划中的每一圈都表示为一对数字i和j，分别表示当前移动中要着色的像素的行和列。

  如果帕夏按照他的计划行事，确定他是否输了，如果输了，确定由黑色像素组成的2×2正方形的移动方向。



pasha loves his phone and also putting his hair up... But the hair is now irrelevant.

Pasha has installed a new game to his phone. The goal of the game is following. There is a rectangular field consisting of n row with m pixels in each row. Initially, all the pixels are colored white. In one move, Pasha can choose any pixel and color it black. In particular, he can choose the pixel that is already black, then after the boy's move the pixel does not change, that is, it remains black. Pasha loses the game when a 2×2 square consisting of black pixels is formed.
Pasha has made a plan of k moves, according to which he will paint pixels. Each turn in his plan is represented as a pair of numbers i and j, denoting respectively the row and the column of the pixel to be colored on the current move.
Determine whether Pasha loses if he acts in accordance with his plan, and if he does, on what move the 2×2 square consisting of black pixels is formed.
Input
The first line of the input contains three integers n,m,k (1≤n,m≤1000, 1≤k≤105)− the number of rows, the number of columns and the number of moves that Pasha is going to perform.
The next k lines contain Pasha's moves in the order he makes them. Each line contains two integers i and j (1≤i≤n, 1≤j≤m), representing the row number and column number of the pixel that was painted during a move.
Output
If Pasha loses, print the number of the move when the 2×2 square consisting of black pixels is formed.
If Pasha doesn't lose, that is, no 2×2 square consisting of black pixels is formed during the given k moves, print 0.
Examples
Input 
2 2 4
1 1
1 2
2 1
2 2
Output 
4
Input 
2 3 6
2 3
2 2
1 3
2 2
1 2
1 1
Output 
5
Input 
5 3 7
2 3
1 2
1 1
4 1
3 1
5 3
3 2
Output 
0


输入格式

输入的第一行包含三个整数n，m，k（1≤n,m≤1000, 1≤k≤105)− 行数、列数和帕夏要执行的移动数。

 

接下来的k行包含了帕夏的动作顺序。每行包含两个整数i和j（1≤i≤n、 1≤j≤m） ，表示移动期间绘制的像素的行号和列号。

 

输出格式

如果帕夏输了，当由黑色像素组成的2×2正方形形成时，打印移动的数字。

如果帕夏没有失败，也就是说，在给定的k次移动中没有形成由黑色像素组成的2×2正方形，则打印0。

输入样例 复制 

2 2 4
1 1
1 2
2 1
2 2

输出样例 复制 

1

数据范围与提示

Input 
2 2 4
1 1
1 2
2 1
2 2
Output 
4
Input 
2 3 6
2 3
2 2
1 3
2 2
1 2
1 1
Output 
5
Input 
5 3 7
2 3
1 2
1 1
4 1
3 1
5 3
3 2
Output 
0

分类标签