6533: BZOJ2533：[Poi2001]Nas Necklaces项链

 项链
著名珠宝商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

提示

没有写明提示

题目来源

没有写明来源