Карта звездного неба Берляндии представляет собой клетчатое поле n × m клеток. В каждой клетке либо есть звезда, либо нет. Любимое созвездие всех берляндских астрономов — созвездие Крест. Это созвездие образуют любые такие 5 различных звезд, что для некоторого целого числа x (радиуса созвездия) выполняется:
Таких различных созвездий может быть очень много, поэтому все они нумеруются целыми числами от единицы следующим образом: при сравнении двух созвездий, меньший номер получает то, радиус которого меньше, при их равенстве — то, средняя звезда которого находится выше средней звезды другого, при равенстве — то, средняя звезда которого левее.
Ваша задача — по заданной карте звездного неба Берляндии найти k-ое по счету созвездие Крест.
В первой строке записаны три целых числа n, m и k (1 ≤ n, m ≤ 300, 1 ≤ k ≤ 3·107) — высота и ширина карты и номер нужного созвездия соответственно. Левый верхний угол имеет координаты (1, 1), а правый нижний — (n, m). Далее следует n строк по m символов — описание карты. j-ый символ в i-ой строке — «*» если в соответствующей клетке звезда, «.» если в соответствующей клетке пусто.
Если на карте меньше k созвездий, выведите -1. Иначе выведите 5 строк по два целых числа в каждой — координаты звезд нужного созвездия. Звезды выводите в порядке: центральная, верхняя, нижняя, левая, правая.
5 6 1 ....*. ...*** ....*. ..*... .***..
2 5 1 5 3 5 2 4 2 6
5 6 2 ....*. ...*** ....*. ..*... .***..
-1
7 7 2 ...*... ....... ...*... *.***.* ...*... ....... ...*...
4 4 1 4 7 4 4 1 4 7
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач