Porównywanie naszyjników

Limit pamięci: 32 MB

W Bajtocji żyje bardzo znany jubiler Bajtazar. Zajmuje się on wyrobem naszyjników. Naszyjniki są zrobione z drogocennych kamieni nanizanych na nitkę. Do wyrobu naszyjników używa się 26 rodzajów kamieni, będziemy je oznaczać małymi literami alfabetu (angielskiego): a, b, ..., z. Bajtazar postawił sobie za punkt honoru, aby nigdy nie wykonać dwóch takich samych naszyjników i przechowuje opisy wykonanych przez siebie naszyjników. Niektóre z tych naszyjników są bardzo długie. Dlatego też ich opisy mają skróconą postać. Każdy opis składa się z szeregu wielokrotnie powtórzonych sekwencji kamieni (wzorów). Opis naszyjnika to ciąg wzorów wraz z liczbami ich powtórzeń. Każdy wzór jest opisany za pomocą sekwencji liter reprezentujących kamienie tworzące wzór. Przykładowo, opis: abc 2 xyz 1 axc 3 reprezentuje naszyjnik abcabcxyzaxcaxcaxc powstały przez dwukrotne powtórzenie wzoru abc, jednokrotne wystąpienie wzoru xyz i trzykrotne powtórzenie wzoru axc. Sprawę dodatkowo utrudnia fakt, iż naszyjniki nie mają widocznego początku, ani końca i można je dowolnie obracać w kółko. Powyższy opis reprezentuje również np. naszyjniki cabcxyzaxcaxcaxcab oraz xcaxcaxcabcabcxyza.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia dwa opisy naszyjników,
• sprawdzi, czy opisy te reprezentują takie same naszyjniki,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym i drugim wierszu standardowego wejścia znajdują się opisy naszyjników, po jednym w wierszu. Każdy z nich składa się z sekwencji liczb całkowitych i słów złożonych z małych liter alfabetu angielskiego, pooddzielanych pojedynczymi odstępami. Opis naszyjnika składa się z liczby całkowitej równej liczbie wzorów występujących w opisie naszyjnika (), po której występuje opisów powtórzeń wzorów. Opis powtórzeń -tego wzoru składa się z: liczby całkowitej równej długości wzoru (), słowa złożonego z małych liter alfabetu (angielskiego) a, ..., z, reprezentującego wzór, oraz liczby całkowitej równej liczbie powtórzeń wzoru (). Wiadomo, że suma liczb (dla ) nie przekracza .

Wyjście

Twój program powinien zapisać, w pierwszym i jedynym wierszu standardowego wyjścia, słowo "TAK", jeśli obydwa opisy przedstawiają taki sam naszyjnik, lub słowo "NIE", w przeciwnym przypadku.

Przykład

Dla danych wejściowych:

3 3 abc 2 3 xyz 1 3 axc 3
4 4 cabc 1 4 xyza 1 3 xca 3 1 b 1

poprawną odpowiedzią jest:

TAK

Autorzy zadania: Adam Malinowski, Wojciech Rytter.