Zadanie Stencle [A} (ste)

Stemple [A]

Limit pamięci: 32 MB

Mały Jaś bawi się swoim małym magicznym stempelkiem, próbując narysować króliczka na kartce rozmiaru na , podzielonej na kwadraciki o boku . Stempelek Jasia ma kształt kwadratu o boku i składa się z mniejszych kwadratów o boku 1. Dokładnie dwa spośród tych kwadratów są wypukłe (tzn. wystające). Co więcej, oba wystające kwadraty znajdują się bądź w tym samym wierszu, bądź kolumnie. Chcąc przy użyciu stempla rysować obrazki, należy przyłożyć go do kartki, tak aby jego wystające kwadraciki trafiły dokładnie w kwadraciki na kartce. Kiedy jakiś wystający kwadracik dotknie kartki, to dotknięty kwadracik na kartce zmienia kolor - z czarnego na biały lub z białego na czarny. Przy przyłożeniu mały stempel może wystawać poza kartkę, ważne aby wystające kwadraciki znalazły się nad kartką. Stempel można przesuwać, ale nie można go obracać.

Początkowo cała kartka jest biała. Króliczek składa się z pewnej liczby kwadracików, które mają być czarne (wszystkie pozostałe kwadraciki muszą być białe). Jaś długo próbował przy pomocy swojego małego stempelka narysować króliczka, ale mu się to nie udawało (nie musi to jednak oznaczać, że jest to niemożliwe, a jedynie że małym stempelkiem ciężko jest ogarnąć taką dużą kartkę!). Poprosił więc o pomoc swojego większego brata, dużego Janka.

Duży Janek może pomóc małemu Jasiowi, dając mu duży magiczny stempel. Duży stempel ma rozmiar na i znajduje się na nim dowolna liczba wystających kwadracików (nie muszą one leżeć tylko w jednym wierszu czy też kolumnie). Stempel ten działa tak samo jak mały stempel Jasia, z jednym dodatkowym ograniczeniem - duży stempel można przystawiać tylko tak, aby w całości znajdował się nad kartką.

Zanim duży Janek da małemu Jasiowi duży stempel, chce upewnić się, że oba stemple naraz wystarczą już do narysowania króliczka. Prosi Cię więc o pomoc.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita () oznaczająca liczbę zestawów testowych. Opis jednego zestawu rozpoczyna się wierszem z dwiema liczbami całkowitymi oraz (, ), oddzielonymi pojedynczym odstępem. Oznaczają one odpowiednio rozmiar stempla dużego Jana oraz rozmiar kartki. Kolejne trzy wiersze zawierają opis stempelka małego Jasia. Każdy z tych wierszy zawiera ciąg trzech znaków 0 lub 1. Opis taki przedstawia wygląd białej kartki, do której przyłożono stempelek: 0~oznacza białe pole, zaś 1 - pole czarne. Dokładnie dwa znaki w tych trzech wierszach są jedynkami i oba znajdują się bądź w tym samym wierszu, bądź kolumnie. Zauważ, że nie jest to wygląd samego stempla - wygląd stempla jest symetrycznym odbiciem figury, którą rysuje on na kartce.

W kolejnych wierszach znajduje się opis stempla dużego Janka w analogicznym formacie, przy czym opis ten może zawierać dowolną liczbę jedynek.

Kolejne wierszy zawiera opis króliczka do narysowania, w takiej samej postaci jak opisy stempli. Jedynka oznacza, że odpowiedni kwadracik kartki powinien być zamalowany, a zero, że kartka w tym miejscu musi być biała.

Wyjście

Dla każdego zestawu testowego na standardowe wyjście wypisz jeden wiersz ze słowem TAK lub NIE, w zależności od tego, czy przy użyciu łącznie obydwu stempli da się narysować podanego w zestawie króliczka.

Przykład

Dla danych wejściowych:

poprawną odpowiedzią jest:

NIE
TAK

Uwaga: W danych testowych użytych do oceny programu rysunki, które próbuje narysować Jaś, mogą w żaden sposób nie przypominać króliczka.

Autor zadania: Jakub Onufry Wojtaszczyk.