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.
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.