Дистанционный практикум по программированию

В лагере, где летом отдыхал Вася, часто устраивали математические бои. Частью таких боёв является игра на конкурс капитанов. Суть игры состоит в следующем. Дано клетчатое поле размером M × N клеток. Двое игроков по очереди ставят крестик в свободную клетку. Проигрывает игрок, после хода которого на поле впервые образовался параллелограмм с вершинами в центрах клеток, помеченных крестиками.

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

Примечание: параллелограмм должен быть невырожденным, то есть никакие три его вершины не лежат на одной прямой.

Входные данные

В первой строке записаны через пробел числа M и N − размеры поля (2 ≤ M, N ≤ 255). В следующих M строках записано по N символов '.' (точка) или 'x' (маленькая латинская буква "икс"), где символ '.' означает пустую клетку, символ 'x' означает клетку, помеченную крестиком.

Примечание: поле не обязательно получено в ходе вышеописанной игры − оно может быть заполнено крестиками произвольным образом.

Выходные данные

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

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

Если параллелограмма на поле нет, то выведите -1.

Пример ввода 1 4 7 .x..... ......x x...... .....x. Пример вывода 1 1 2 2 7 4 6 3 1

Пример ввода 2 4 5 ..... .xxxx ..... ...x. Пример вывода 2 -1

Система оценивания.

Подзадача 1 (до 50 баллов): 2 ≤ M, N ≤ 20.

Подзадача 2 (до 25 баллов): 2 ≤ M, N ≤ 50.

Подзадача 3 (до 25 баллов): 2 ≤ M, N ≤ 255.