Archiwum zadań programistycznych WWSI

Wykreślanka - rodzaj zabawy słownej, polegającej na odnajdywaniu i wykreślaniu ukrytych w diagramach słów, które najczęściej podano obok bloku z literami. Wyrazy można odczytywać w kolumnach, wierszach i po skosach, a także wspak. Wykreślanki początkowo kierowano do najmłodszych szaradzistów, umieszczając pojedyncze zagadki w magazynach z krzyżówkami. Obecnie ten rodzaj zabawy doczekał się wydań poświęconych tylko tej formie rozrywki, a jej odbiorcami stali się także dorośli.

Od dziś wykreślanki będą miały jeszcze jedną formę - elektroniczną, a do grona odbiorców dołączą studenci informatyki. Nasza wersja różni się jednak nieco od oryginału. Wykreślance wyrazy mogą się "zawijać" np. część wyrazu może znajdować się na końcu wiersza/kolumny, a reszta na początku (i odwrotnie przy wyrazach czytanych wspak). Możemy traktować to tak jakby macierz z literami naciągnięta była na walec poziomy dla kolumn i pionowy dla wierszy. Dodatkowo w naszej zabawie nie można wykreślać wyrazów po ukosie.

Wejście

W pierwszej linii wejścia znajduje się dokładnie jedna liczba całkowita Z (1 ≤ Z ≤ 10) określająca liczbę zestawów danych.

Każdy zestaw danych w pierwszej linii zawiera liczbę r (1 ≤ r ≤ 1000) określającą rozmiar tablicy z literami (r × r). W następnych r liniach znajduje się opis tablicy. W kolejnym wierszu znajduje się liczba p (1 ≤ p ≤ 400) – ilość wyrazów, których będziemy poszukiwać. W kolejnych p liniach znajdują się poszukiwane wyrazy. Długość wyrazu nie przekracza 2000 znaków. Każda komórka wczytanej tabeli może zostać wykorzystana tylko raz w danym wyrazie.

Wyjście

Na wyjściu należy w oddzielnej linii dla każdego wyrazu wypisać słowo TAK jeżeli znajduje się on w tablicy lub słowo NIE w przeciwnym wypadku.

Przykład

Wejście:

1
3
ABC
QAZ
WSX
5
ABC
XBAZ
XCZ
ZAQ
WSA

Wyjście:

TAK
NIE
TAK
TAK
NIE