Necklaces

Byteland is famous for the beautiful necklaces crafted by the jeweler Byteman. Each necklace is a loop of gemstones strung together. There are 26 kinds of stones, written as the lowercase Latin letters a to z (stones of the same kind are indistinguishable). Byteman never makes two identical necklaces, so he keeps a description of every necklace he has ever produced.

Because some necklaces are very long, their descriptions are stored in a compressed form. A description is a sequence of fragments. Each fragment is a pattern (a string of letters) together with an integer telling how many times that pattern repeats, and the necklace is obtained by concatenating the fragments in order. For example, a description whose patterns are abc repeated 2 times, xyz repeated 1 time, and axc repeated 3 times encodes the necklace abcabcxyzaxcaxcaxc.

The difficulty is that a necklace is a loop: there is no fixed starting stone, so the loop may be read starting from any position (the necklace can be rotated). Two descriptions therefore represent the same necklace when one loop can be rotated into the other. For instance, the necklace above can also be written as cabcxyzaxcaxcaxcab or xcaxcaxcabcabcxyza.

Given two descriptions, decide whether they encode the same necklace.

The input has two lines, one description per line. A description is a list of tokens separated by single spaces. It starts with an integer $n$, the number of patterns ($1 \le n \le 1000$), followed by $n$ pattern blocks. The $i$-th block has three tokens: an integer $l_i$, the length of the pattern ($1 \le l_i \le 10000$); the pattern $s_i$, a string of exactly $l_i$ lowercase letters; and an integer $k_i$, the number of times the pattern repeats ($1 \le k_i \le 100000$). For each description, the sum of all $l_i$ is at most $10000$.

Print a single line: TAK (Polish for "yes") if the two descriptions encode the same necklace, or NIE (Polish for "no") otherwise.