Viruses

The Binary Viruses Investigation Committee discovered that certain sequences of zeroes and ones are virus codes. The committee has isolated the set of all virus codes. A sequence of zeroes and ones is called safe if none of its segments (a segment is a sequence of consecutive elements) equals a virus code. The committee wants to determine whether an infinite, safe sequence of zeroes and ones exists.

Write a program that:

• reads the virus codes from standard input,
• determines whether an infinite, safe sequence of zeroes and ones exists,
• writes the result to standard output.

The first line contains a single integer $n$, the number of virus codes. Each of the next $n$ lines contains one non-empty word made of 0s and 1s - a virus code. The total length of all words does not exceed $30000$.

Print a single word on the only line of standard output:

• TAK - if an infinite, safe sequence of zeroes and ones exists.
• NIE - otherwise.

For the set of codes $\{011, 11, 00000\}$, one example of a safe infinite sequence is $010101\ldots$. For the set of codes $\{01, 11, 00000\}$, no safe infinite sequence of zeroes and ones exists.