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