Codeforces Beta Round 35 (Div. 2) |
---|
Закончено |
После ужасающего лесного пожара в Берляндии была реализована программа восстановления леса, по которой были посажены N рядов по M деревьев в каждом, причем настолько ровно, что можно ввести систему координат, в которой j-тое дерево в i-м ряду будет иметь координаты (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, записанные через пробел, — координаты дерева, которое загорится последним. Если таких деревьев несколько, выведите любое из них.
3 3
1
2 2
1 1
3 3
1
1 1
3 3
3 3
2
1 1 3 3
2 2
Название |
---|