Две самые далёкие метки

На поле $n \times m$ отмечены звёздочками не менее двух клеток.

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

В первой строке числа $n$ и $m$ от $1$ до $1000$. В следующих $n$ строках по $m$ символов — точки и звёздочки.

Одно число.

Перебирать пары меток нельзя: их может быть до полумиллиона. Заметьте, что $|r_1 - r_2| + |c_1 - c_2|$ равно наибольшему из двух выражений: разности величин $r + c$ и разности величин $r - c$. Значит достаточно найти по полю четыре крайних значения.