开始: 2026-03-23 00:00:00

25-26赛季联合赛04

结束: 2026-03-26 00:00:00
当前  2026-04-05 04:26:12  类型: IOI  状态: 已经结束 

P6. 森林着火
描述

n\times m 棵树组成的矩形,初始时有 K 棵树被点燃了。

如果一棵树有相邻的树被点燃,在一分钟之后,这棵树也会被点燃。

问最晚点燃的树的坐标(数字最小的一组,先比x坐标,如果x坐标相同,比y坐标)。


输入

第一个输入行包含两个整数 n,m(1\le n,m\le 2000)

第二行包含一个整数 K(1\le K\le 10),表示初始时被点燃的树的个数。

第三行包含 K 对整数 X_1,Y_1,X_2,Y_2,...,X_K,Y_K,表示初始时被点燃的树的坐标,保证没有两个坐标重合。


输出

用两个空格分隔的整数输出一行 XY,即最后一个被点燃的树的坐标。

样例

输入

3 3
1
2 2

输出

1 1

输入

3 3
1
1 1

输出

3 3

输入

3 3
2
1 1 3 3

输出

1 3
提示

样例3,虽然有三个点都是最后点燃的,但是由于最小的限制,所以输出1,3

数据范围:

本题一共有10个测试点;

测试点#1-3:数据保证一开始着火的肯定只有一个点 n,m(1\le n,m\le 2000),k=1

测试点#4-6: n,m(1\le n,m\le 20),k\leq 10

测试点#7-10: n,m(1\le n,m\le 2000),k\leq 10


提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交