题目描述

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 \times k \le 5\,000\,000$），之间用一个空格分隔。分别表示城镇名称的位数和不对应任何城镇的 $n$ 位序列的数量。

第二行包含两个字符串，之间用一个空格分隔，每个字符串由 $n$ 个字符 0 和/或 1 组成。这两个字符串是城镇 $x$ 和 $y$ 的名称。

接下来的 $k$ 行中，给出了所有不对应任何城镇的 $n$ 位序列，每行一个序列。每个这样的序列是一个由 $n$ 个字符 0 和/或 1 组成的字符串。你可以假设 $x$ 和 $y$ 不在这些 $k$ 个序列中。

输出格式

你的程序应向标准输出输出单词 TAK（波兰语中的“是”），如果从城镇 $x$ 步行到城镇 $y$ 是可能的；否则输出单词 NIE（波兰语中的“否”）。

4 6
0000 1011
0110
0111
0011
1101
1010
1001

TAK