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
#include <cstdio>
#include <cstring>
using namespace std;

bool is_palindrome(char *str, int size) {
	for (int i = 0; i < size; ++i) {
		if (str[i] != str[size - i - 1]) {
			return false;
		}
	}
	return true;
}

bool is_palindrome(unsigned *arr, int size) {
	for (int i = 0; i < size; ++i) {
		if (arr[i] != arr[size - i - 1]) {
			return false;
		}
	}
	return true;
}

int hash(char *str, int begin, int end, bool inverse) {
	unsigned res = 0, MOD = 165190913;	
	if (!inverse) {
		for (int i = begin; i != end; ++i) {
			res = 26 * res + (str[i] - 'a') % MOD;
		}
	}
	else {
		for (int i = end - 1; i >= begin; --i) {
			res = 26 * res + (str[i] - 'a') % MOD;
		}
	}
	return res;
}


int main() {
	int n;
	scanf("%i", &n);
	bool result;
	if (n != 0) {
		if (n < 3000000) {
			char str[n + 1];
			scanf("%s", str);
			result = is_palindrome(str, n);
		}
		else {
			int SIZE = 750000, SEG = 27;
			int index = 0, cnt = 0, seg_cnt = 0;
			unsigned int arr[SIZE];
			char c, segment[SEG];
			while ((c = getchar()) != -1) {
				if (c == '\n')
					continue;
				if (cnt != n/2 || n % 2 != 1) {
					segment[seg_cnt] = c;
					++seg_cnt;
				}
				++cnt;
				if (seg_cnt >= SEG || cnt == n/2 || cnt == n/2 + n/2 % SEG + n % 2) {
					arr[index] = hash(segment, 0, seg_cnt, cnt > n/2);
					seg_cnt = 0;
					++index;
				}
			}
			//printf("%i %i %u\n", index, cnt, arr[index - 1]);
			result = is_palindrome(arr, index);
		}
	}
	else {
		int SIZE = 3000001;
		char str[SIZE];
		scanf("%s", str);
		result = is_palindrome(str, strlen(str));
	}

	if (result)
		printf("TAK\n");
	else
		printf("NIE\n");
	
    return 0;
}