Logo

Limit pamięci: 32 MB

Ostatnimi laty w Bajtocji nastąpił burzliwy rozwój wolnego rynku i powstało wiele nowych firm. Prawie każda firma umieszcza przed wejściem do swojej siedziby wielki szyld z logo firmy. Logo firmy projektuje się na prostokątnej siatce podzielonej na kwadraty, zaczernianiając stosowne kwadraty. Następnie, na podstawie tak przygotowanego projektu tworzony jest szyld: na prostokątnym tle naklejane są płaty ze złota w taki sposób, aby otrzymana figura miała dokładnie kształt zaprojetowanego logo (kształt figury zadanej przez czarne kwadraty w projekcie). Płaty można obracać i przyklejać dowolną stroną. Nie można jednak naklejać jednych płatów na inne. Każdy jednostkowy kwadrat w projekcie odpowiada złotemu kwadratowi wielkości m m. Produkcją szyldów zajmuje się firma LogoBajt. Do budowy szyldów firma LogoBajt używa złotych płatów o kilku kształtach. Płat w każdym kształcie jest w jednym kawałku i składa się z pewnej liczby jednostkowych kwadratów ( m m). Tutaj "jeden kawałek" oznacza, że w płacie można przejść od każdego kwadratu do każdego innego pokonując ciąg kwadratów, z kórych każde kolejne dwa mają wspólną krawędź. Płaty wytłaczane są z matryc wielkości m m poprzez wycięcie niektórych spośród dziewięciu jednostkowych kwadratów. Firma LogoBajt właśnie otrzymała pewną liczbę zamówień na nowe szyldy. Twoim zadaniem jest określenie dla każdego spośród nich, czy da się go wykonać mając do dyspozycji tylko płaty o zadanych kształtach. Jeśli tak, to jaka jest najmniejsza liczba płatów, z których można zbudować szyld.

Zadanie

Napisz program, który:

• wczyta opis kształtów płatów używanych w firmie LogoBajt,
• wczyta projekty szyldów,
• dla każdego projektu stwierdzi, czy jest on wykonalny, a jeśli tak, to obliczy minimalną liczbę płatów potrzebnych do jego wykonania,
• wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się liczba całkowita , równa liczbie opisów kształtów płatów stsosowanych w firmie LogoBajt, . Następnie mamy pusty wiersz, a po nim opisy wszystkich stosowanych kształtów. Między kolejnymi dwoma opisami znajduje się jeden pusty wiersz.

Opis jednego kształtu mieści się w trzech wierszach, zawierających po znaki: znak # oznacza, że odpowiadający mu kwadrat jednostkowy należy do płata, znak . (kropka) oznacza, że taki kwadrat jest wycinany z matrycy.

Po wszystkich opisach płatów mamy znowu pusty wiersz, a następnie pojawia się wiersz z liczbą zamówień (). Dalej jest znów pusty wiersz oraz opisy wszystkich projektów, oddzielone pojedynczymi pustymi wierszami.

Opis projektu zaczyna się od dwóch liczb , oddzielonych odstępem (, ). Są to odpowiednio szerokość i wysokość projektowanego szyldu w metrach. W każdym z kolejnych wierszy znajduje się znaków: znak # oznacza, że odpowiadający mu kwadrat powinien być złoty, znak . (kropka) oznacza, że to miejsce powinno pozostać puste.

Wyjście

Na wyjściu powinno znaleźć się dokładnie wierszy. W -tym wierszu powinieneś wypisać, albo minimalną liczbę płatów potrzebnych do wyprodukowania -teg szyldu opisanego na wejściu, albo jedno słowo NIE, jeśli projektu nie da się zrealizować.

Przykład

Dla danych wejściowych:

2

###
..#
...

...
#..
...

1

12 4
###..#...###
#.#..#...#.#
###..#...###
#.#..###.#.#

poprawną odpowiedzią jest:

11