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

typedef unsigned long long ULL;

const ULL M31 = (1ULL << 31) - 1;

// palindrom: a1 a2 a3 a4 a3 a2 a1
// forward hash: a1*b^6 + a2*b^5 + ... a2*b^1+ a1*b^0
// backward hash: a1*b^0 + a2*b^1 + ... + a2*b^5 + a1*b^6

ULL mod_M31(ULL val)
{
    val = (val & M31) + (val>>31);
    return (val >= M31) ? val - M31 : val;
}

void hash_forward(ULL &hash, unsigned b, unsigned c)
{
    hash = mod_M31(hash * b + c);
}

void hash_backward(ULL &hash, ULL &b_pow, unsigned b, unsigned c)
{
	hash = mod_M31(hash + b_pow*c);
	b_pow = mod_M31(b_pow * b);
}

int main() {

    unsigned b1 = 31;
    ULL b1_pow = 1;
    unsigned b2 = 107;
    ULL b2_pow = 1; 
    unsigned b3 = 104729;
    ULL b3_pow = 1;
    unsigned b4 = 611953;
    ULL b4_pow = 1; 

    // forward, backward
    ULL hash1f = 0;
    ULL hash1b = 0;
    ULL hash2f = 0;
    ULL hash2b = 0;
    ULL hash3f = 0;
    ULL hash3b = 0;
    ULL hash4f = 0;
    ULL hash4b = 0;

    int N;
    scanf("%d\n", &N);

    // int count = 0;

    const int BUF_SIZE = 3*1<<20;
    char buffer[BUF_SIZE+1];
    while (fgets(buffer, BUF_SIZE, stdin))
    {
        for (int i = 0; 'a' <= buffer[i] && buffer[i] <= 'z'; ++i)
        {
                char c = buffer[i];
                hash_forward(hash1f, b1, c - 'a');
                hash_backward(hash1b, b1_pow, b1, c - 'a');

                hash_forward(hash2f, b2, c - 'a');
                hash_backward(hash2b, b2_pow, b2, c - 'a');

                hash_forward(hash3f, b3, c - 'a');
                hash_backward(hash3b, b3_pow, b3, c - 'a');

                hash_forward(hash4f, b4, c - 'a');
                hash_backward(hash4b, b4_pow, b4, c - 'a');

                // count++;
        }
    }

    /*
    int count = (hash1f == hash1b ? 1:0) + (hash2f == hash2b ? 1:0) +
            (hash3f == hash3b ? 1:0) + (hash4f == hash4b ? 1:0);

    if (count != 0 && count != 4)
    {
        printf("ERROR %d\n", count);
        return 1;
    }
    */

	puts((hash1f == hash1b && hash2f == hash2b &&
          hash3f == hash3b && hash4f == hash4b) ? "TAK" : "NIE");

    return 0;
}