Problem description


Pokrycie słowne
(pokrycie-slowne)
Memory limit: 32 MB
Time limit: 0.50 s

Jak już wiesz z lektury poprzednich zadań Jasio uwielbia zabawy słowami. Tym razem wymyślił następującą: mając dany słownik dozwolonych słów oraz słowo S, zastanawia się, czy słowo S może powstać jako konkatenacja (sklejenie) pewnych słów ze słownika. Słów ze słownika wolno używać wielokrotnie. Oczywiście takich pytań jest wiele i to dla całkiem wielu różnych słów S.

Napisz program, który: wczyta słownik dozwolonych słów oraz słowa, które Jasio chce uzyskać, dla każdego z tych słów wyznaczy czy jest możliwe jego uzyskanie za pomocą słów ze słownika i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca liczbę słów w słowniku. W kolejnych N wierszach znajdują się niepuste ciągi małych liter alfabetu angielskiego – słowa w słowniku. W kolejnym wierszu znajduje się jedna liczba naturalna Q, określająca liczbę zapytań. W kolejnych Q wierszach znajdują się niepuste ciągi małych liter alfabetu angielskiego – zapytania Jasia.

Wyjście

Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym wierszu powinna się znaleźć odpowiedź TAK, jeśli jest możliwe uzyskanie słowa z i-tego zapytania za pomocą słów ze słownika, zaś NIE w przeciwnym przypadku.

Ograniczenia

1 ≤ N ≤ 500, 1 ≤ Q ≤ 100.

Długość słowa w słowniku nie przekracza 1 000 znaków. Długość zapytania nie przekracza 5 000 znaków.

Przykład

Input Output Explanation
4
anna
mama
nana
nan
4
ananas
nananan
mamama
annanannana
NIE
TAK
NIE
TAK

nana nan, anna nan nana