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