Walk

The names of towns in Byteotia are distinct binary strings of exactly $n$ bits. There are $2^n - k$ towns in Byteotia, so exactly $k$ of the length-$n$ bit sequences name no town.

Some pairs of towns are directly connected by roads. Precisely, two towns are directly linked by a road if and only if their names differ in exactly one bit. Roads never cross outside of towns.

Byteasar wants to take a stroll from town $x$ to town $y$, walking only along existing roads. Write a program that decides whether such a walk from $x$ to $y$ is possible.

The first line contains two integers $n$ and $k$ separated by a single space ($1 \le n \le 60$, $0 \le k \le 1{,}000{,}000$, $k \le 2^n - 1$, $n \cdot k \le 5{,}000{,}000$). Here $n$ is the length of a town name in bits and $k$ is the number of length-$n$ bit sequences that name no town.

The second line contains two strings separated by a single space, each a name of length $n$ over the characters 0 and 1. These are the names of towns $x$ and $y$.

Each of the next $k$ lines contains one length-$n$ bit sequence that names no town, one per line, each a string of 0 and 1. Neither $x$ nor $y$ appears among these $k$ sequences.

Print TAK (Polish for yes) on a single line if a walk from town $x$ to town $y$ is possible, and NIE (Polish for no) otherwise.

For instance, here are two possible walks from $0000$ to $1011$:

• $0000 \to 1000 \to 1100 \to 1110 \to 1111 \to 1011$
• $0000 \to 0100 \to 1100 \to 1110 \to 1111 \to 1011$