Карта звездного неба Берляндии представляет собой клетчатое поле n × m клеток. В каждой клетке либо есть звезда, либо нет. Любимое созвездие всех берляндских астрономов — созвездие Крест. Это созвездие образуют любые такие 5 различных звезд, что для некоторого целого числа x (радиуса созвездия) выполняется:
- 2-ая находится в той же вертикали что и 1-ая, но на x клеток выше
- 3-я находится в той же вертикали что и 1-ая, но на x клеток ниже
- 4-ая находится в той же горизонтали что и 1-ая, но на x клеток левее
- 5-ая находится в той же горизонтали что и 1-ая, но на x клеток правее
Таких различных созвездий может быть очень много, поэтому все они нумеруются целыми числами от единицы следующим образом: при сравнении двух созвездий, меньший номер получает то, радиус которого меньше, при их равенстве — то, средняя звезда которого находится выше средней звезды другого, при равенстве — то, средняя звезда которого левее.
Ваша задача — по заданной карте звездного неба Берляндии найти k-ое по счету созвездие Крест.
Выходные данные
Если на карте меньше k созвездий, выведите -1. Иначе выведите 5 строк по два целых числа в каждой — координаты звезд нужного созвездия. Звезды выводите в порядке: центральная, верхняя, нижняя, левая, правая.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 6 1
....*.
...***
....*.
..*...
.***..
|
2 5
1 5
3 5
2 4
2 6
|
|
2
|
5 6 2
....*.
...***
....*.
..*...
.***..
|
-1
|
|
3
|
7 7 2
...*...
.......
...*...
*.***.*
...*...
.......
...*...
|
4 4
1 4
7 4
4 1
4 7
|