#3421. Poi2013 Walk

题目描述

The names of towns in Byteotia are unique sequences of exactly N bits. There are 2^N - k towns in Byteotia, and thus, only K sequences of N bits do not correspond to any town.
Some pairs of towns are connected with roads. Specifically, two towns are directly linked by a road if and only if their names differ in a single bit. The roads do not cross outside of towns.
Byteasar intends to take a stroll - he intends to walk from the town x to the town y , taking the existing roads. Your task is to write a program that will determine if such a walk is possible.

有2^N-k个点，每个点有一个独一无二的、长度为n的01串，但是有k个01串没有出现过。每两个点之间有连边当且仅当两个01串之间有且仅有一个位置是不同的。现在询问x和y两个字符串能不能互相到达

输入格式

In the first line of the standard input, there are two integers, N and K (1<=N<=60,0<=K<=1000000,k<=2^N-1, N*k<=5000000) separated by a single space. These are the length of town names in bits and the the number of N -bit sequences that do not correspond to any town, respectively. In the second line, there are two strings, separated by a single space, each consisting of characters 0 and/or 1. These are the names of the towns x and y. In the K lines that follow, all the sequences of N bits that do not correspond to any town are given, one sequence per line. Each such sequence is a string of characters 0 and/or1. You may assume that x and y are not among those K sequences.

输出格式

Your program should print to the standard output the word TAK (Polish for yes) if walking from the town x to the town y is possible, and the word NIE (Polish for no) otherwise.

样例

样例输入

4 6  

0000 1011  

0110  

0111  

0011  

1101  

1010  

1001  

样例输出

TAK  

数据范围与提示