Pieczątki

Limit pamięci: 64 MB

Bituś od dłuższego czasu bawił się, zamalowując pisakiem niektóre pola na papierze w kratkę. Uzyskane w ten sposób pikselowe obrazki wieszał nad łóżkiem i zapowiedział, że nie przestanie, póki będzie tam jeszcze wolne miejsce.

Jego mama uważała, że zabiera to chłopcu zbyt dużo czasu, więc postanowiła mu pomóc - przyniosła ze strychu pieczątki, którymi kiedyś sama się bawiła. Każda taka pieczątka, po przyciśnięciu do kartki, "zamalowywała" jakiś, zawsze taki sam, wzór z pól. Bitusiowi pieczątki spodobały się, ale nie jest pewien, czy wystarczą do wykonania jego nowego obrazka.

Wiedząc, jak ma wyglądać nowy obrazek oraz znając wzory odciskane przez pieczątki, określ, czy Bituś może go ukończyć bez używania pisaka. Bituś nie obraca pieczątek (patrz drugi test przykładowy). Pamiętaj, że obrazek nie zajmuje całej kartki, ale żadne pole, które nie należy do obrazka, nie powinno być zamalowane (patrz pierwsze dwa testy przykładowe).

Wejście

W pierwszym wierwszu standardowego wejścia znajdują się wymiary obrazka - dwie liczby: i ().

W kolejnych wierszach znajduje się po znaków "#" lub ".", informujących odpowiednio, że dane pole musi być odciśnięte co najmniej raz albo że musi być pozostawione puste.

W następnym wierszu znajduje się jedna liczba (), oznaczająca liczbę pieczątek do dyspozycji Bitusia.

Opis każdej pieczątki jest podobny do opisu obrazka - składa się z dwóch liczb: i (), oznaczających wymiary pieczątki oraz wierszy po znaków "#" lub ".", oznaczających, że przyłożenie pieczątki w odpowiednim miejscu zamaluje wszystkie pola znajdujące się pod znakami "#", nie zmieniając stanu tych położonych pod znakami ".".

W przypadkach testowych wartych łącznie punktów pieczątki będą zamalowywały obszary kwadratowe.

W przypadkach testowych wartych łącznie punktów pieczątki będą zamalowywały obszary prostokątne.

W przypadkach testowych wartych łącznie punktów każda pieczątka będzie posiadała co najmniej jeden "#" na każdej ścianie opisu.

Wyjście

Na standardowe wyjście należy wypisać jedno słowo - "TAK", jeśli podane pieczątki wystarczą do namalowania obrazka, "NIE", w przeciwnym wypadku.

Przykłady

Dla danych wejściowych:

5 5
..#..
.###.
..#..
..###
..#..
2
3 5
.....
.###.
.....
4 1
#
#
#
#

poprawną odpowiedzią jest:

TAK

Dla danych wejściowych:

6 6
##....
######
.####.
.#####
.##.##
.#....
1
2 2
##
#.

poprawną odpowiedzią jest:

NIE

Dla danych wejściowych:

5 13
#####.#.#####
#...#.#.#....
#...#.#.#.###
#...#.#.#...#
#####.#.#####
4
3 3
.#.
###
.#.
3 5
#...#
#....
#...#
1 3
###
2 5
....#
#####

poprawną odpowiedzią jest:

TAK

Autor zadania: Jakub Pachocki.