← 返回题目列表

Codeforces · 35/C

C. 再次开火

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

Berland 发生可怕的森林火灾后,实施了森林重生计划。因此,种植了 N 行,每行有 M 棵树,而且行非常整齐,以至于可以将其映射到坐标系上,以便第 i 行中的第 j 棵树的坐标为 (i, j)。然而,可怕的事情发生了,年轻的森林着火了。现在我们必须找到最后着火的树的坐标来计划疏散。

K点同时开始燃烧,这意味着最初有K棵树开始燃烧。每一分钟,火都会从燃烧的树木蔓延到未燃烧的树木,并且它们到最近的燃烧树木的距离等于 1。

找到最后开始燃烧的树。如果有多个这样的树,则输出任何一个。

输入

第一输入行包含两个整数 N, M (1 ≤ N, M ≤ 2000) — 森林的大小。树木种植在 (x, y) (1 ≤ x ≤ N, 1 ≤ y ≤ M) 类型的所有点上,x 和 y 是整数。

第二行包含一个整数 K (1 ≤ K ≤ 10) — 开始时燃烧的树木数量。

第三行包含 K 对整数:x1, y1, x2, y2, ..., xk, yk (1 ≤ xi ≤ N, 1 ≤ yi ≤ M) — 起火点的坐标。保证没有两点重合。

输出

输出一行,其中包含两个空格分隔的整数 x 和 y——最后一棵开始燃烧的树的坐标。如果有多个这样的树,则输出任何一个。

示例

输入 #1

3 3
1
2 2

输出 #1

1 1

输入 #2

3 3
1
1 1

输出 #2

3 3

输入 #3

3 3
2
1 1 3 3

输出 #3

2 2