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

#define DBG(...) fprintf(stderr, __VA_ARGS__)

typedef int I;
static const I MAXL = 20000000;
static const I BUFL = MAXL / 4 + 123;

static std::bitset<BUFL * 5> buf; // 3MB

static inline void ins(I pos, I c) {
        if (pos > MAXL/2)
                return;
        I ix = (pos % BUFL) * 5;
        for (I i=0; i<5; ++i)
                buf[ix + i] = !!(c & (1u << i));
}

static inline I get(I pos) {
        I ix = (pos % BUFL) * 5;
        I ret = 0;
        for (I i=0; i<5; ++i)
                ret |= (buf[ix + i] << i);
        return ret;
}

static inline bool next(I& i) {
        I c = getchar();
        if (c < 'a' || c > 'z')
                return false;
        i = c - 'a';
        return true;
}

template <I d, I q>
struct rollinghash {
        I left, right, h;

        bool equal() const {
                return left == right;
        }

        void init(I c1, I c2) {
                h = 1;
                left = c1 % q;
                right = c2 % q;
        }

        void even(I c, I half) {
                right = (d * (right + q - (h * half) % q) % q + c) % q;
        }

        void odd(I c, I half) {
                h = (h * d) % q;
                left  = (left + (h * half) % q) % q;
                right = ((right * d) % q + c) % q;
        }
};

static bool check() {
        rollinghash<32, 103> h1;
        rollinghash<32, 83> h2;
        {
                I c1, c2;
                if (!next(c1) || !next(c2))
                        return true;
                ins(0, c1);
                ins(1, c2);
                h1.init(c1, c2);
                h2.init(c1, c2);
        }
        for (I pos=2;; ++pos) {
                I c;
                if (!next(c))
                        return h1.equal() && h2.equal();
                ins(pos, c);
                I half = get(pos / 2);
                if (pos & 1) {
                        h1.odd(c, half);
                        h2.odd(c, half);
                } else {
                        h1.even(c, half);
                        h2.even(c, half);
                }
        }
}

int main() {
        I N;
        scanf("%u\n", &N);
        printf(check() ? "TAK\n" : "NIE\n");
        return 0;
}