D. Созвездие
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Карта звездного неба Берляндии представляет собой клетчатое поле n × m клеток. В каждой клетке либо есть звезда, либо нет. Любимое созвездие всех берляндских астрономов — созвездие Крест. Это созвездие образуют любые такие 5 различных звезд, что для некоторого целого числа x (радиуса созвездия) выполняется:

  • 2-ая находится в той же вертикали что и 1-ая, но на x клеток выше
  • 3-я находится в той же вертикали что и 1-ая, но на x клеток ниже
  • 4-ая находится в той же горизонтали что и 1-ая, но на x клеток левее
  • 5-ая находится в той же горизонтали что и 1-ая, но на 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