Pasha and Pixels

题意翻译

现在有一个n*m 的矩阵,一开始全部格子被染成白色。 接下来有k个操作,每一个操作表示把一个格子染成黑色。 输入n,m和k,接下来k行,每行两个正整数x,y,表示要染成黑色的格子的坐标; 输出一个正整数,为第一次出现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.

输入输出格式

输入格式


The first line of the input contains three integers $ n,m,k $ ( $ 1<=n,m<=1000 $ , $ 1<=k<=10^{5} $ ) — 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.

输出格式


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 $ .

输入输出样例

输入样例 #1

2 2 4
1 1
1 2
2 1
2 2

输出样例 #1

4

输入样例 #2

2 3 6
2 3
2 2
1 3
2 2
1 2
1 1

输出样例 #2

5

输入样例 #3

5 3 7
2 3
1 2
1 1
4 1
3 1
5 3
3 2

输出样例 #3

0