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
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <vector>

using namespace std;

const long long x_0 = 257;
const long long mod_0 = 1337000011;
long long h1_0 = 0;
long long h2_0 = 0;
long long pow_0 = 1;

const long long x_1 = 263;
const long long mod_1 = 1337000059;
long long h1_1 = 0;
long long h2_1 = 0;
long long pow_1 = 1;

unsigned long long ux = 887;
unsigned long long uh1 = 0;
unsigned long long uh2 = 0;
unsigned long long upow = 1;

void process(char c) {
    uh1 = uh1 + c * upow;
    upow = upow * ux;
    uh2 = uh2 * ux + c;

    h1_0 = (h1_0 + c * pow_0) % mod_0;
    pow_0 = (pow_0 * x_0) % mod_0;
    h2_0 = (h2_0 * x_0 + c) % mod_0;

    h1_1 = (h1_1 + c * pow_1) % mod_1;
    pow_1 = (pow_1 * x_1) % mod_1;
    h2_1 = (h2_1 * x_1 + c) % mod_1;
}

bool is_pal() {
    //printf("%lld %lld\n", uh1, uh2);
    //printf("%lld %lld\n", h1_0, h2_0);
    //printf("%lld %lld\n", h1_1, h2_1);
    if (uh1 != uh2) {
        return false;
    }
    if (h1_0 != h2_0) {
        return false;
    }
    if (h1_1 != h2_1) {
        return false;
    }
    return true;
}

int main() {
    while (true) {
        char c = getchar_unlocked();
        if (c == EOF) {
            break;
        } else if (isdigit(c)) {
            // skip digits from first line
        } else if (isalpha(c)) {
            process(c);
        }
        // skip line delimiters and garbage
    }
    if (is_pal()) {
        printf("TAK\n");
    } else {
        printf("NIE\n");
    }
    return 0;
}