FRAKTAL - konkurs programistyczny

Foordle to obecnie najpopularniejsza gra we Fraktalocji. Gra posiada słownik n wyrazów 5-literowych. Jako wyraz rozumiemy dowolny ciąg liter alfabetu angielskiego. Gra losuje jeden wyraz ze słownika, a zadaniem gracza jest go odgadnąć. Gracz próbuje odgadnąć szukany wyraz podając wyrazy ze słownika. Po każdej próbie odgadnięcia gracz otrzymuje 5-cyfrowy ciąg mogący zawierać cyfry: 0, 1, 2. Cyfra i-ta w kolejności określa informację zwrotną dla litery znajdującej się na i-tej pozycji w wyrazie jaki podał zawodnik. Cyfry mają następujące znaczenie:

• 0 - Podana litera nie występuje w szukanym wyrazie.
• 1 - Podana litera występuje w szukanym wyrazie, ale nie na tej pozycji.
• 2 - Podana litera występuje w szukanym wyrazie na tej pozycji. Innymi słowy została poprawnie odgadnięta.

Maciek wykonał już q prób odgadnięcia wyrazu. Dla każdej z nich otrzymał 5-cyfrowy ciąg z informacją zwrotną.

Odpowiedz na pytanie, czy otrzymane informacje zwrotne są wystarczające, żeby w następnej próbie odgadnąć szukany wyraz?

Wejście

W pierwszej linii wejścia znajduje się liczba wyrazów w słowniku n ∈ [2, 10⁵].

W kolejnych n liniach znajdują się wyrazy jakie zawiera słownik. Każdy wyraz składa się z 5 wielkich liter alfabetu angielskiego.

W następnej linii wejścia znajduje się liczba prób odgadnięcia wyrazu q ∈ [1, n).

W każdej z kolejnych q linii znajduje się wyraz ze słownika jaki podał Maciek próbując odgadnąć hasło oraz 5-cyfrowy ciąg z informacją zwrotną dla podanego wyrazu.

Wyjście

Jeżeli otrzymane informacje są wystarczające, żeby w następnej próbie odgadnąć szukany wyraz to na wyjściu należy wypisać TAK X, gdzie X to szukany wyraz. W przeciwnym wypadku należy wypisać NIE.

Przykład 1

Wejście:

5
HABED
FRAKT
FABAZ
BAFAG
BAFAH
2
HABED 02100
FABAZ 12120

Wyjście:

TAK BAFAG

Wyjaśnienie do przykładu:

Z informacji zwrotnych wiemy, że:

• Litera A występuje w szukanym wyrazie na pozycjach 2 i 4.
• Litera B występuje w szukanym wyrazie na pozycji innej niż 3.
• Litera F występuje w szukanym wyrazie na pozycji innej niż 1.
• Litery D, E, H, Z nie występują w szukanym wyrazie.

Na podstawie tych informacji możemy wywnioskować, że jedynym wyrazem spełniającym wszystkie warunki jest BAFAG.

Przykład 2

Wejście:

6
HAGED
FRAKT
BAGAF
FABAZ
BAFAG
FABAG
1
FABAZ 12120

Wyjście:

NIE