Problem description


Literkowa zupa
(D)
Limit pamięci: 256 MB
Limit czasu: 2.00 s

Ulubioną zupą Jasia jest zupa literkowa (zupa pomidorowa z makaronem w kształcie liter). Sympatia Jasia do tej zupy wynika z możliwości grania w gry słowne podczas jedzenia. Ponieważ Mama Jasia ugotowała dla niego dzisiaj tę zupę, Jasio od razu zabrał się do jej konsumpcji. W tym momencie w zupie znajduje się dziewięć liter, które ułożyły się w kształt kraty 3x3. Jasio wymyślił pewne słowo S i zaczął się zastanawiać, czy jest w stanie jednym zgrabnym ruchem nabrać to słowo na łyżkę.

Ruch nazwiemy zgrabnym, jeśli każda nabrana na łyżkę litera (poza pierwszą) -– przed rozpoczęciem nabierania liter –- znajdowała się obok poprzedniej nabranej litery. Formalnie, niech Zi, j oznacza literę znajdującą się w i–tym wierszu oraz j–tej kolumnie kraty. Wtedy dla każdej pary kolejnych liter Zi1, j1 oraz Zi2, j2 musi zachodzić warunek |i1i2| + |j1j2| = 1.

Pomóż Jasiowi ustalić, czy jest w stanie nabrać na łyżkę słowo S jednym zgrabnym ruchem, zaczynając od litery znajdującej się w pierwszym wierszu i pierwszej kolumnie kraty (Z1, 1).

Wejście

W pierwszym wierszu wejścia znajduje się wymyślone przez Jasia słowo S.
W następnych trzech wierszach znadują się trzyliterowe słowa będące opisem położenia liter w zupie. j–tą literę w i–tym wierszu oznaczamy przez Zi, j.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinno się znaleźć TAK, jeżeli jest możliwe zagarnięcie literek na łyżkę, aby znajdowało się na niej słowo S, lub NIE w przeciwnym przypadku.

Ograniczenia

Słowo S ma dziewięć liter. Zi mają po trzy litery. S oraz Z zawierają wyłącznie litery alfabetu angielskiego.

Przykład

Wejście Wyjście Wyjaśnienie
literkowa
lit
kre
owa
TAK

Ilustracja na początku treści prezentuje ruchy łyżką potrzebne do zagarnięcia “literkowa” na łyżkę.