FRAKTAL - konkurs programistyczny

Jaś przegląda słownik języka polskiego, wybiera losowe słowa i łączy je w jedno długie słowo, które następnie zapisał na komputerze. Kiedy spał, jego siostra postanowiła zrobić mu psikusa i dopisała losowe znaki do tak utworzonego słowa.

Kiedy Jaś odkrył co się wydarzyło, postanowił udowodnić, że nowo postałe słowo nadal da się utworzyć łącząc ze sobą wybrane słowa ze słownika.

Znając słowo Jasia zmodyfikowane przez jego siostrę i mając listę dostępnych słów określ, czy to jest możliwe (każde słowe ze słownika można wykorzystać wielokrotnie).

Wejście

Na wejściu pojawi się słowo Jasia o długości nie większej niż 10010 składające się tylko z wielkich liter alfabetu angielskiego.

Następnie podano liczbę n (n < 150 000) - ilość słów w słowniku.

W kolejnych n liniach znajdują się różne słowa ze słownika. Każde pojedyncze słowo jest niedłuższe niż badane słowo i składa się tylko z wielkich liter alfabetu angielskiego.

Uwaga: Żaden plik testowy nie jest większy niż 11MB!

Wyjście

Na wyjściu należy wypisać NIE, jeśli nie da się stworzyć słowa Jasia ze słów ze słownika lub wypisać kolejno słowa, które po połączeniu utworzą słowo Jasia (każde prawidłowe rozwiązanie zostanie zaakceptowane).

Przykład 1

FRAKTALTOMOJULUBIONYKONKURS
9
INFORMATYCZNA
FRAKTAL
MOJ
TO
ULUBIONY
KONKURS
OLIMPIADA
FRAKTALTOMOJU
LUBIONYKONKURS

FRAKTAL TO MOJ ULUBIONY KONKURS

FRAKTALTOMOJU LUBIONYKONKURS

Przykład 2

KTOTOTAKI
3
T
KTO
TAKI

NIE