题目描述

题目译自 XX Olimpiada Informatyczna — II etap Spacer

Bajtocja 的城市名称由 $n$ 位二进制串组成，每座城市名称各不相同。Bajtocja 共有 $2^n - k$ 座城市，因此有 $k$ 个不同的 $n$ 位二进制串不是城市名称。

某些城市之间通过道路连接，这些道路仅在城市处相交。两座城市直接连接的条件是它们的名称仅差一位。

Bajtazar 计划从城市 $x$ 漫步到城市 $y$，仅使用现有道路。你的任务是编写程序，判断这样的漫步是否可行。

---

输入格式

第一行包含两个整数 $n$, $k$（$1 \leq n \leq 60$，$0 \leq k \leq 1\,000\,000$，$k < 2^n - 1$，$n \cdot k \leq 5\,000\,000$），分别表示城市名称的位数和非城市名称的二进制串数量。

第二行包含两个由 $n$ 个 01 字符组成的字符串，用单个空格分隔，表示城市 $x$ 和 $y$ 的名称。

接下来的 $k$ 行，每行包含一个由 $n$ 个 01 字符组成的字符串，表示非城市名称的二进制串。

保证城市 $x$ 和 $y$ 的名称不在 $k$ 个非城市二进制串中。

---

输出格式

若可从城市 $x$ 漫步到城市 $y$，输出 TAK；否则输出 NIE。

---

样例 1

输入

4 6
0000 1011
0110
0111
0011
1101
1010
1001

输出

TAK

以下是从城市 $0000$ 到城市 $1011$ 的示例路线：

$0000 → 1000 → 1100 → 1110 → 1111 → 1011$

$0000 → 0100 → 1100 → 1110 → 1111 → 1011$

---

样例 2

输入

2 2
00 11
01
10

输出

NIE

---

附加样例

1.$n=20$, $k=215766$，禁止所有 $0$ 的个数能被 $5$ 整除的城市，$x=100\ldots0$, $y=011\ldots1$，答案为 NIE。

2.$n=50$, $k=100000$，$x$ 和 $y$ 直接连接，答案为 TAK。

3.$n=60$，答案为 TAK。

---

数据范围与提示

对于 $25\%$ 的数据，$n \leq 22$。