Лена — красивая девушка, которая любит логические головоломки.
В подарок на день рождения Лена получила матрицу-головоломку!
Матрица состоит из \(n\) строк и \(m\) столбцов, и каждая ячейка либо черная, либо белая. Координаты \((i,j)\) обозначает ячейку, которая находится в \(i\)-й строке и \(j\)-м столбце для любых \(1\leq i \leq n\) и \(1\leq j \leq m\). Чтобы решить головоломку, Лена должна выбрать какую-то ячейку так, чтобы минимизировать манхэттенское расстояние от этой ячейки до самой дальней от нее черной клетки.
Более формально, пусть в матрице \(k \ge 1\) черных ячеек с координатами \((x_i,y_i)\) для каждого \(1\leq i \leq k\). Лене нужно так выбрать ячейку \((a,b)\), чтобы минимизировать \(\)\max_{i=1}^{k}(|a-x_i|+|b-y_i|).\(\)
Поскольку у Лены нет нужных навыков, она попросила вас о помощи. Скажите ей оптимальную клетку, которую нужно выбрать.
Выходные данные
Для каждого набора входных данных выведите оптимальную ячейку \((a,b)\). Если существует несколько оптимальных ответов, выведите любой.
Примечание
В первом наборе входных данных две черные клетки имеют координаты \((1,1)\) и \((3,2)\). Четыре оптимальные ячейки: \((1,2)\), \((2,1)\), \((2,2)\) и \((3,1)\). Можно показать, что никакая другая ячейка не минимизирует максимальное манхэттенское расстояние до самой дальней черной клетки.
Во втором наборе входных данных оптимально выбрать черную клетку \((2,2)\) с максимальным манхэттенским расстоянием \(2\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 2
BW
WW
WB
3 3
WWB
WBW
BWW
2 3
BBB
BBB
5 5
BWBWB
WBWBW
BWBWB
WBWBW
BWBWB
9 9
WWWWWWWWW
WWWWWWWWW
BWWWWWWWW
WWWWWWWWW
WWWWBWWWW
WWWWWWWWW
WWWWWWWWW
WWWWWWWWW
WWWWWWWWB
|
2 1
2 2
1 2
3 3
6 5
|