#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int HSIZE = 5e6 + 11,
EMPTY = 0,
KMAX = 500009;
int N, K, fprev[KMAX], fhash[KMAX], vprev[HSIZE], vhash[HSIZE], vfree = 1, ffree = 1;
ll x, y, forbidden[KMAX], vis[HSIZE], Q[HSIZE];
void hashSetInsert(ll *S, int *prev, int *Hash, int &free, ll val, int sz) {
S[free] = val;
prev[free] = Hash[val % sz];
Hash[val % sz] = free++;
}
bool hashSetLookup(ll *S, int *prev, int *Hash, ll val, int sz) {
for(int i = Hash[val % sz]; i > 0; i = prev[i])
if(S[i] == val)
return true;
return false;
}
void hashSetClear(int *Hash, int &free, int sz) {
free = 1;
for(int i = 0; i < sz; ++i)
Hash[i] = 0;
}
bool graphSearch(ll s, ll d, int bound) {
int b = 0, e = 0, c = 1;
Q[e++] = s;
hashSetInsert(vis, vprev, vhash, vfree, s, HSIZE);
while(b < e && c < bound) {
ll v = Q[b++];
for(int i = 0; i < N; ++i) {
ll next = v ^ (1LL << i);
if(next == d)
return true;
if(!hashSetLookup(forbidden, fprev, fhash, next, KMAX) && !hashSetLookup(vis, vprev, vhash, next, HSIZE)) {
Q[e++] = next;
hashSetInsert(vis, vprev, vhash, vfree, next, HSIZE);
++c;
}
}
}
if(c >= bound)
return true;
return false;
}
bool solve(ll s, ll d) {
int bound = N * K + 1;
bool a = graphSearch(s, d, bound);
hashSetClear(vhash, vfree, HSIZE);
bool b = graphSearch(d, s, bound);
return a && b;
}
ll readBin() {
string s;
cin >> s;
ll nr = 0;
for(int i = N - 1; i >= 0; --i)
if(s[i] == '1')
nr += (1LL << (N - i - 1));
return nr;
}
void read() {
cin >> N >> K;
x = readBin(), y = readBin();
for(int i = 0; i < K; ++i) {
ll a;
a = readBin();
hashSetInsert(forbidden, fprev, fhash, ffree, a, KMAX);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
read();
if(solve(x, y))
cout << "TAK";
else
cout << "NIE";
}
