Избранный, призванный восстановить Пламя и завершить этот цикл возжигания и угасания, должен на своем пути сразиться с множеством могущественных врагов.

Несмотря на известный факт, что все бои с боссами очень сложны, в некоторых случаях можно выбить и более легкую победу, если применить нестандартную тактику. Так, дракон Мидир Пожиратель Тьмы может быть намного проще побежден с помощью заклинания «Ядовитый туман», которое позволит заметно сократить длительность боя, нанося дракону постоянный урон.

Представим поле сражения с драконом в виде прямоугольной сетки размера $$$n \times m$$$ ($$$n$$$ строк и $$$m$$$ столбцов) и обозначим за $$$(i, j)$$$ клетку поля на пересечении $$$i$$$-й слева строки и $$$j$$$-го сверху столбца. Также назовем соседними клетки поля, имеющие общую сторону.

Определим расстояние между двумя клетками $$$A$$$ и $$$B$$$ как минимальное такое $$$k$$$, что существует последовательность клеток $$$C_0, C_1, \ldots, C_k$$$, в которой $$$C_0 = A$$$, $$$C_k = B$$$ и любые два $$$C_i$$$ и $$$C_{i+1}$$$ — соседние. Так, расстояние между $$$(1, 2)$$$ и $$$(4, 1)$$$ равно $$$4$$$, так как из одной в другую можно попасть за четыре перемещения: $$$(1, 2) \to (2, 2) \to (3, 2) \to (3, 1) \to (4, 1)$$$.

Перед началом боя, то есть пока вы еще не оказались на поле, вы можете подойти к любой клетке $$$A$$$ на его границе (то есть к клетке, хотя бы одна из сторон которой находится на границе поля) и создать на ней ядовитый туман. Туман распространяется из каждой клетки во все соседние с ней за одну секунду, пока не заполнит все поле. Таким образом, время, за которое туман распространится до произвольной клетки $$$B$$$, равно расстоянию между $$$A$$$ и $$$B$$$.

Вы не хотите долго ходить вокруг поля и ждать начала боя, поэтому вам необходимо определить координаты клетки, в которой следует создать ядовитый туман, чтобы он заполнил все поле за минимальное время.

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены. Обратите внимание, что прохождение тестов из условия не является необходимым для тестирования на некоторых группах тестов.