Девочка Надя очень любит играть мозаикой, поэтому у неё
есть множество различных вариантов мозаики. Как-то раз её младшая сестра
высыпала несколько мозаик в одну кучку и как следует эту кучку перемешала, а
так как отдельные элементы всех мозаик имеют одинаковый размер базового
элемента (квадрат 1 × 1) и одинаковый цвет, то разделить
элементы обратно стало невозможно.
Каждая мозаика укладывается в квадратную коробку с
размером стороны N (2 ≤ N ≤ 5).
Отдельный элемент мозаики состоит из квадратов 1 × 1, соединённых
таким образом, что из любого квадрата элемента до любого другого его квадрата
можно дойти, переходя через общие стороны квадратов, принадлежащих элементу.
Количество квадратов в одном элементе не менее 1 и не более N 2.
Кроме того, каждый элемент имеет такую форму и размеры, что взятый отдельно он
помещается в пустую коробку из-под мозаики.
Надя берёт пустую коробку и выбирает K
элементов (1 ≤ K ≤ N 2)
таким образом, чтобы каждый из них подходил к данной коробке и, кроме того,
суммарное количество квадратов у данных элементов равнялось ровно N 2.
Теперь Наде остаётся лишь придумать вариант укладки элементов в коробку или понять,
что это невозможно. В первом случае выбранные элементы можно считать единой
мозаикой, а во втором — следует выбрать другие элементы.
Вам требуется помочь Наде уложить выбранные элементы в
коробку. Элементы при укладывании разрешается двигать, вращать на угол кратный
90 градусам и переворачивать на другую сторону.
Формат входных и выходных данных
Первая строка входных данных содержит числа
N и K, разделённые пробелом. В последующих строках следуют
описания K элементов мозаики. Описания отдельных элементов разделены
пустой строкой.
Каждый элемент представлен уложенным произвольным
образом в коробку из-под мозаики. Описание элемента представляет собой N
строк по N символов в каждой. Символ '.'
(точка) соответствует пустой клетке коробки, а символ '*' (звёздочка) — клетке элемента.
Выходные данные должны содержать описание любой
допустимой укладки элементов в коробку или число 0, если укладка невозможна.
Описание укладки представляет собой N строк по N разделённых
пробелами чисел в каждой. Каждое число описывает номер элемента, который
занимает соответствующую клетку коробки. Элементы нумеруются в порядке
следования во входных данных, начиная с 1.
Примеры
|
Входные данные
|
Выходные данные
|
|
2 2
**
..
*.
*.
|
1
1
2
2
|
|
3
2
***
***
.*.
...
*..
*..
|
0
|
Условия всех задач XVI межвузовской олимпиады в одном файле
