Byteotia 的城镇名称是长度恰好为 $n$ 的唯一比特序列。Byteotia 共有 $2^n-k$ 个城镇，因此有 $k$ 个长度为 $n$ 的比特序列不对应任何城镇。

某些城镇之间由道路连接。具体来说，当且仅当两个城镇的名称仅有一位不同时，它们之间有道路直接相连。道路不会在城镇之外交叉。

Byteasar 打算去散步——他计划沿着现有的道路从城镇 $x$ 走到城镇 $y$。你的任务是编写一个程序，判断这样的路径是否存在。

输入格式

第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 60$, $0 \le k \le 1\,000\,000$, $k \le 2^n-1$, $n \cdot k \le 5\,000\,000$)，用空格分隔。它们分别表示城镇名称的比特长度以及不对应任何城镇的 $n$ 位序列的数量。第二行包含两个由空格分隔的字符串，每个字符串由 $n$ 个字符 '0' 或 '1' 组成，分别表示城镇 $x$ 和 $y$ 的名称。接下来的 $k$ 行中，每行给出一个不对应任何城镇的 $n$ 位序列。你可以假设 $x$ 和 $y$ 不在这些序列中。

输出格式

如果从城镇 $x$ 到城镇 $y$ 的路径存在，程序应输出 TAK（波兰语中的“是”），否则输出 NIE（波兰语中的“否”）。

样例

输入 1

4 6
0000 1011
0110
0111
0011
1101
1010
1001

输出 1

TAK

输入 2

2 2
00 11
01
10

输出 2

NIE

说明

以下是从 0000 到 1011 的两条路径示例：

• 0000 → 1000 → 1100 → 1110 → 1111 → 1011
• 0000 → 0100 → 1100 → 1110 → 1111 → 1011