Задача B. Отладка шарика ≡

Условие

Юный программист Вася решил разработать собственную платформу виртуальной реальности. Для начала он реализовал вывод пустой чёрной сцены с единственным красным шаром. Однако в алгоритме вывода шара Вася допустил ошибки, из-за которых шар не всегда выводился правильно.

Для отладки Вася сделал скриншоты своего приложения (шар на них должен превратиться в круг). Скриншот представлен прямоугольным массивом символов, в котором символ "#" представляет красный пиксель, а символ "." — чёрный пиксель.

Если шар нарисован правильно, то красными будут только те пиксели, координаты которых (x; y) удовлетворяют условию (x − x₀)² + (y − y₀)² ≤ r², где x₀, y₀, r — неизвестные целые числа.

Требуется написать программу, которая по изображению выяснит, правильно ли на нём нарисован шар (спроецированный в круг), и если да, то определит значения x₀, y₀, r.

Формат входных данных

Первая строка входных данных содержит целые числа X Y — ширину и высоту прямоугольника. Следующие Y строк содержат по X символов "#" и "." каждая — описание изображения.

Формат выходных данных

Выходные данные должны содержать целые числа 1x₀ y₀ r, если изображение является правильным, и число 0 в противном случае. Координаты отсчитываются от верхнего левого угла.

Ограничения

3 ≤ X, Y ≤ 2000, r ≥ 1

1 ≤ x₀ − r < x₀ + r ≤ X, 1 ≤ y₀ − r < y₀ + r ≤ Y

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

3 3
.#.
###
.#.

1 2 2 1