Аркадий играет в «Морской бой». Несмотря на это, большую часть правил этой игры вам знать необязательно.
Вам дано поле, состоящее из $$$n \times n$$$ клеток. На поле должен находиться ровно один $$$k$$$-палубник, т. е. корабль длиной $$$k$$$ клеток, ориентированный горизонтально или вертикально. Но Аркадий не знает, где этот корабль находится. Для каждой клетки Аркадий знает, точно ли она пустая или же она может содержать часть корабля.
Рассмотрим все возможные расположения корабля. Найдите такую клетку, которая принадлежит максимально возможному числу разных расположений корабля.
В первой строке содержится два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le k \le n \le 100$$$) — размер поля и размер корабля.
Следующие $$$n$$$ строк содержат поле. В каждой строке содержится $$$n$$$ символов, каждый из которых либо «#» (обозначает определённо пустую клетку) или «.» (обозначает клетку, которая может принадлежать кораблю).
Выведите два целых числа — номер строки и номер столбца клетки, которая принадлежит максимальному числу возможных разных расположений корабля.
Если есть несколько возможных вариантов ответа, выведите любой из них. В частности, если корабль не может располагаться на поле, вы можете вывести любую клетку.
4 3
#..#
#.#.
....
.###
3 2
10 4
#....##...
.#...#....
..#..#..#.
...#.#....
.#..##.#..
.....#...#
...#.##...
.#...#.#..
.....#..#.
...#.#...#
6 1
19 6
##..............###
#......#####.....##
.....#########.....
....###########....
...#############...
..###############..
.#################.
.#################.
.#################.
.#################.
#####....##....####
####............###
####............###
#####...####...####
.#####..####..#####
...###........###..
....###########....
.........##........
#.................#
1 8
Рисунок ниже показывает три возможных различных положения корабля, содержащих клетку $$$(3, 2)$$$ в первом примере.
Название |
---|