1954. Мозаика

Девочка Надя очень любит играть мозаикой, поэтому у неё есть множество различных вариантов мозаики. Как-то раз её младшая сестра высыпала несколько мозаик в одну кучку и как следует эту кучку перемешала, а так как отдельные элементы всех мозаик имеют одинаковый размер базового элемента (квадрат 1x1) и одинаковый цвет, то разделить элементы обратно стало невозможно.

Каждая мозаика укладывается в квадратную коробку с размером стороны `N` (`2\ ≤\ N\ ≤\ 5`). Отдельный элемент мозаики состоит из квадратов 1x1, соединённых таким образом, что из любого квадрата элемента до любого другого его квадрата можно дойти, переходя через общие стороны квадратов, принадлежащих элементу. Количество квадратов в одном элементе не менее 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