VIII Olimpiada Informatyczna 2000/2001
Zadanie: NAS
Autor: Adam Malinowski, Wojciech Rytter
Naszyjniki
Zawody III stopnia, dzień pierwszy 27 marzec 2001
Plik źródłowy: NAS.??? (np. pas, c, cpp)
Plik wykonywalny: NAS.exe
Plik wejściowy: NAS.in
Plik wyjściowy: NAS.out

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-ciu rodzajów kamieni, będziemy je oznaczać małymi literami alfabetu (angielskiego): a-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:

Wejście

W pierwszym i drugim wierszu pliku tekstowego nas.in 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 n równej liczbie wzorów występujących w opisie naszyjnika (1<=n<=1 000), po której występuje n opisów powtórzeń wzorów. Opis powtórzeń i-tego wzoru składa się z: liczby całkowitej li równej długości wzoru (1<=li<=10 000), słowa si złożonego z li małych liter alfabetu (angielskiego) a-z, reprezentującego wzór oraz liczby całkowitej ki równej liczbie powtórzeń wzoru si (1<=ki<=100 000). Wiadomo, że suma liczb li (dla i=1,...,n) nie przekracza 10 000.

Wyjście

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

Przykład

Dla pliku wejściowego nas.in: 
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 plik wyjściowy nas.out 
TAK