Задача D. Поучительный фильм ≡

Условие

Учителю Иванову пришло указание вместо уроков отвести M учеников своего класса в кино на просмотр поучительного фильма "О пользе хорошего поведения". Учитель опасается, что тема фильма не вызовет достаточно большого интереса у школьников, и они начнут хулиганить.

Кресла в зале кинотеатра расположены в N рядов по N мест в каждом. Определим расстояние между креслами как сумму модулей разностей номеров рядов и номеров мест.

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

Рекомендуется рассмотреть частичные решения

1. M = 1
2. N ≤ 100

Формат входного файла

Первая строка входного файла содержит целые числа N M. Следующие N строк содержат по N символов '.' (ASCII 46) и '#' (ASCII 35) каждая, обозначающих соответственно свободное и занятое место. Ряды нумеруются от 1 до N сверху вниз, места нумеруются от 1 до N слева направо.

Формат выходного файла

Выходной файл должен содержать целое число R — наименьшее возможное максимальное расстояние. Далее должна следовать M + 1 пара чисел — номера рядов и мест сначала для учителя, затем для учеников.

Если учеников рассадить невозможно, выведите единственное число 0. Если существует несколько оптимальных решений, выведите любое из них.

Ограничения

1 ≤ M ≤ 10⁶; 1 ≤ N ≤ 2000

Примеры тестов

4 8
....
..#.
....
###.

2
2 2
1 1
1 2
1 3
2 1
2 4
3 1
3 2
3 3

2 2
##
#.

0