1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <cstdio>
#include <bitset>
#include <iostream>
#include <limits>
using namespace std;

long n = 0;
long chars_written = 0;
bitset<20000000> bits;

bool idx_equal_char(long idx, char a) {
	//cout << "checking: " << idx << ", for: " << a<< endl;
	int ia = a - 'a';
	int k = 0;
	while (ia > 0) {
		if (bits[idx*5 + k] != (ia & 1)) {
		//	cout << "found diff at "<< k << ", " << bits[idx*5 + k]<< ", "<< (ia & 1) << endl;
			return false;
		}
		ia = ia >> 1;
		k ++;
	}
	return true;
}

bool idx_equal(long idx1, long idx2) {
	for (int k=0; k <5; k++) {
		if (bits[idx1*5 + k] != bits[idx2*5+k]) {
			return false;
		}
	}
	return true;
}

void write_and_shift(char a) {
	int ia = a - 'a';
	int k = 0;
	while (ia > 0) {
		bits.set(chars_written*5 + k, ia & 1);
		ia = ia >> 1;
		k ++;
	}
	chars_written ++;
}

void read() {
	char a;
	scanf("%ld\n", &n);
	if (n == 0) {
		while(cin >> a) {
			write_and_shift(a);
		}
	} else {

		for (long i =0; i<n / 2; i++) {
		    cin >> a;
			write_and_shift(a);
		  //  cout << "read: "<< a << ", chars_written=" << chars_written << endl;
		  //  cout << bits << endl;
		}
		if (n % 2 == 1) {
			cin >> a;
		}
	}
}

bool is_palindrom() {
	if (n == 0) {
		for (long i=0; i<chars_written / 2; i++) {
			if (!idx_equal(i, chars_written - i - 1)) {
				return false;
			}
		}
	} else {
		long indb = 0;
		char a;
		for (long i =0; i<n/2; i++) {
		    cin >> a;
		  //  cout << "read verify: " << a << endl;
		    if (!idx_equal_char(chars_written - indb - 1, a)) {
		    	return false;
		    }
		    indb ++;
		}
	}
	return true;
}

int main() {
  read();
  bool result = is_palindrom();
 // cout << bits << endl;
  if (result) {
	  printf("TAK\n");
  } else {
	  printf("NIE\n");
  }
  return 0;
}