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
96
97
98
99
#include <iostream>
#include <bitset>
#include <functional>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

string s;
size_t h[5010];
hash<string> str_hash;

vector<uint16_t> bs;


int main() {
  ios::sync_with_stdio(false);

  int i, n;
  char c;
  bool pal = true;

  cin >> n;

  if(n == 0) {
    i = 0;

    while(cin >> c) {
      if(i % 3 == 0) {
        bs.push_back(0);
      }
      uint16_t x = bs[i / 3];
      x += (c - 'a') * pow(32, i % 3);
      bs[i / 3] = x;
      i++;
    }
    
    n = i;

    for(int i = 0; i < n / 2; i++) {
      uint16_t a, b;
      int index = i;
      a = bs[index/3];
      for(int j = 0; j < index % 3; j++) {
        a /= 32;
      }
      a %= 32;

      index = n - i - 1;
      b = bs[index/3];
      for(int j = 0; j < index % 3; j++) {
        b /= 32;
      }
      b %= 32;

      if(a != b) {
        pal = false;
        break;
      }
    }
    
    cout << (pal ? "TAK" : "NIE");
  } else {
    s = "";

    for(i = 1; i <= n/2; i++) {
      cin >> c;
      s += c;
      if(i%5000 == 0) {
        h[i/5000] = str_hash(s);
        s = "";
      }
    }

    h[i/5000+1] = str_hash(s);
    s = "";
    i--;
    
    if(n % 2 == 1) { cin >> c; }

    for(; i > 0; i--) {
      cin >> c;
      s += c;
      if(i%5000 == 1) {
        reverse(s.begin(), s.end());
        if(h[i/5000 + 1] != str_hash(s)) {
          pal = false;
        }
        s = "";
      }
    }

    cout << (pal ? "TAK" : "NIE");
  }

  return 0;
}