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
#include <iostream>

using namespace std;

int n;
char c;
unsigned long long begHash[3], endHash[3];
unsigned long long ex = 31, ex2 = 41, ex3 = 43, currentExp = 1, currentExp2 = 1, currentExp3 = 1;

bool isPal() {
    bool result = true;

    for (int i = 0; i < 3; i++) {
        if (begHash[i] != endHash[i]) {
            result = false;
        }
    }

    return result;
}

int toIn(char cc) {
    return (int)cc - (int)'a' + 1;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin >> n;

    while (cin >> c) {
        begHash[0] += toIn(c) * currentExp;
        endHash[0] = endHash[0] * ex + toIn(c);

        begHash[1] += toIn(c) * currentExp2;
        endHash[1] = endHash[1] * ex2 + toIn(c);

        begHash[2] += toIn(c) * currentExp3;
        endHash[2] = endHash[2] * ex3 + toIn(c);

        currentExp *= ex;
        currentExp2 *= ex2;
        currentExp3 *= ex3;
    }

    if (isPal()) {
        cout << "TAK\n";
    } else {
        cout << "NIE\n";
    }

    return 0;
}