← 返回题目列表

Codeforces · 508/A

A. 帕夏和像素

中文机器翻译题面 查看原题

Pasha 喜欢他的手机,也喜欢把头发盘起来……但头发现在已经无关紧要了。

Pasha 已在他的手机上安装了一款新游戏。游戏的目标如下。有一个由 n 行组成的矩形区域,每行有 m 个像素。最初,所有像素都是白色的。帕夏只需一步即可选择任何像素并将其涂成黑色。特别是,他可以选择已经是黑色的像素,那么男孩移动后该像素不会改变,即保持黑色。当由黑色像素组成的 2 × 2 正方形形成时,Pasha 输掉了游戏。

Pasha 制定了 k 个动作的计划,根据该计划他将绘制像素。他的计划中的每一回合都表示为一对数字 i 和 j,分别表示当前移动中要着色的像素的行和列。

判断帕夏如果按照计划行动是否会输,如果输了,则在哪一步棋中形成由黑色像素组成的 2 × 2 正方形。

输入

输入的第一行包含三个整数 n、m、k (1 ≤ n, m ≤ 1000, 1 ≤ k ≤ 105) — 行数、列数以及 Pasha 将执行的移动次数。

接下来的 k 行按照 Pasha 的动作顺序包含他的动作。每行包含两个整数 i 和 j (1 ≤ i ≤ n, 1 ≤ j ≤ m),表示移动过程中绘制的像素的行号和列号。

输出

如果 Pasha 输了,则打印由黑色像素组成的 2 × 2 正方形形成时的移动次数。

如果Pasha没有输,即在给定的k步时间内没有形成由黑色像素组成的2×2正方形,则打印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