题目描述

题目译自 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 1000000, k < 2^n - 1, n \cdot k \leq 5000000)$，分别表示城市名称的位数和非城市名称的二进制串数量。

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

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

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

输出格式

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

4 6
0000 1011
0110
0111
0011
1101
1010
1001

TAK

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

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

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$。