Фермер Джон решил украсить свой дом. Посетив местный китайский магазинчик,
увидел стеклянную фигурку коровы и решил её купить.
Форма этой коровы описывается решёткой из \(N \times N\) символов
(\(3 \leq N \leq 8\)), пример показан ниже, где символы '#' представляют
часть коровы, а символы '.' не части коровы.
...............
...............
...............
#..#...........
####...........
############...
.##.#########..
....#######.##.
....##...##....
....##...##....
...............
...............
...............
...............
...............
К несчастью, ФД ещё не спел купить корову, как в магазинчик ворвался бык,
который поломал всё вокруг, включая корову ФД. Корова разломалась на две части,
которые затерялись среди других \(K\) (\(3 \leq K \leq 10\)) кусков стекла на полу.
Каждый из этих \(K\) кусков описывается решёткой \(N \times N\) символов, как и
исходная фигурка.
Помогите ФД определить, какие из этих \(K\) кусков являются двумя частями
фигурки ФД. При падении на землю куски ФД не поворачивались и не переворачивались,
поэтому для их сборки ФД должен только сдвигать куски горизонтально или вертикально.
Куски не могут наезжать друг на друга и должны сформировать точно исходную фигуру.
ФД может двигать оба куска горизонтально и/или вертикально на любое количество позиций, но так, чтобы все символы '#' оставались внутри решётки \(N \times N\).
Форма каждого из кусков необязательно состоит из связного региона символов '#'.
Но при сдвиге все они сдвигаются на одинаковое количество позиций.
ФОРМАТ ВВОДА (файл bcs.in):
Первая строка ввода содержит \(N\) и \(K\). Следующие \(N\) строк описывают
исходную фигурку ФД. Следующие \(KN\) строк задают \(K\) решёток символов,
описывающих \(K\) кусков, которые ФД нашёл на полу.
ФОРМАТ ВЫВОДА (файл bcs.out):
Выведите одну строку, содержащую два разделённых пробелом целых числа,
каждое в интервале \(1 \ldots K\), указывающих индексы двух кусков коровы ФД.
Решение всегда существует и уникально. Числа, которые Вы выведете, должны
быть в порядке возрастания.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 3
####
#..#
#.##
....
.#..
.#..
##..
....
####
##..
#..#
####
....
.###
.#..
.#..
|
1 3
|