[Poi2001]Nas Necklaces项链

时间限制:5s      空间限制:128MB

题目描述

项链
著名珠宝商Byteman的迷人项链使得Byteland声名在外。这些项链由宝石串织而成。宝石有26个不同的种类
我们用小写的拉丁字母a – z来表示(同一类型的宝石是不可区分的)。不生产俩条完全一样的项链是
Byteman的一份荣誉,因而他保留有以前制造的所有项链的描述。由于有些项链确实很长,这就使得我们
必须用简短的形式来描述它。每个描述都由下列形式的fragments构成:一个字符串(我们称之为pattern)
后面跟一整数,整数表示此pattern在项链中重复的次数。所有描述都是这样的fragments的连续。
例如,描述:
abc 2 xyz 1 axc 3
表示项链abcabcxyzaxcaxcaxc(这一字符串可由写“abc”两次,“xyz”一次和“axc”3次而得到)。
然而,由于不能决定项链的开始(即项链能任意被转动),这个问题变得更加复杂化。一些项链可能
有多于一种的描述形式。例如,我们上面提到的项链也可以描述为如下形式:
cabcxyzaxcaxcaxcab或者xcaxcaxcabcabcxyza。
要求
写一程序:
1、 从文件NAS.IN中读入俩条项链的描述;
2、证明这俩个描述是否表示同一项链;
3、结果写入文件NAS.OUT中。


输入格式

输入俩行。每行都为某一项链的描述,由小写的拉丁字母和整数组成
用单个空格隔开。每行开始为一整数n,它表示此描述中所含pattern的数量
1<=n<=1 000。后面跟着是n个重复pattern的描述。第i个重复pattern由以下几部分组成:
整数li ,表示pattern的长度;由li 个小写拉丁字母构成的字符串si ;
以及整数ki表示pattern在描述中重复的次数,1<=ki<=100 000。整数li (for i=1,...,n)的总和不超过10 000。


输出格式

如果这俩个描述表示的是同一条项链,程序应在输出文件的第一行写入一单词"TAK",否则,写入单词"NIE"。

		


样例输入

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


 

样例输出

TAK

提示

没有写明提示


题目来源

没有写明来源