Polish version    English version  
  History of OI -> VIII OI 2000/2001


 News
 About Olympic
 History of OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
Stage III - results
Stage II - results
Stage I - results
Problems
Regulations
Organization
Hints
Schedule
Stats
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 OI books
 National team
 Olympic camps
 Photo gallery
 Links
 SIO
 MAIN
VIII Olimpiada Informatyczna 2000/2001

Task: NAS
Author: Adam Malinowski, Wojciech Rytter
Necklaces

III stage contest, the first day  

Byteland is known for the gorgeous necklaces made by famous jeweler Byteman. These necklaces are made of gem stones threaded together. The gem stones are divided into 26 distinct sorts, these will be denoted by the lower case Latin letters: a - z (stones of the same sort are indistinguishable). It is a point of honor with Byteman never to produce two identical necklaces, therefore he keeps the descriptions of all the necklaces he had ever produced. Some of the necklaces are really long, that is why their descriptions are kept in a shorten form. Each description consists of fragments of the following form: a sequence of letters (called pattern) followed by an integer denoting the number of times the pattern repeats in the necklace. Every description is a sequence of such fragments. For example, the description:

abc 2 xyz 1 axc 3

represents the necklace abcabcxyzaxcaxcaxc (this word is obtained by writing : "abc" - twice, "xyz" - once, and "axc" - 3 times). The problem is more complicated because of the inability to determine the beginning of the necklace (i.e. the necklace can be arbitrarily turned around). Hence some necklaces may have more then one description. For example, the necklace described above may also be described as: cabcxyzaxcaxcaxcab or xcaxcaxcabcabcxyza.

Task

Write a program which:
  • reads two descriptions of necklaces from the input file NAS.IN,
  • verifies, whether these descriptions represent the same necklace,
  • writes the result in the output file NAS.OUT. 

Input

The text file NAS.IN consists of two lines. Each of these lines is a description of a necklace composed of words of lower case letters from Latin alphabet and integers, separated by single spaces. The description of a necklace begins with integer n equal to the number of patterns in the description, (1<=n<=1 000), followed by n descriptions of repeating patterns. The i-th description of a repeating pattern is composed of: an integer li equal to the length of the pattern, (1<=li<=10 000), a word si built of li lower case Latin letters (a-z) representing the pattern, and an integer ki equal to the number of times the pattern si repeats in the description, (1<=ki<=100 000). The sum of numbers li (for i=1,...,n) des not exceed 10 000.

 

Output

Your program should write in the first and only line of the output file NAS.OUT a word "TAK" ("YES" in Polish), if both descriptions represent the same necklace, and a word "NIE" ("NO" in Polish) if the described necklaces are different.

Example

For the input file 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
the correct answer is the output file NAS.OUT:
TAK



Print friendly version