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
#include <bitset>
using namespace std;
#define MAXN 3120007
char single;
bitset<MAXN*8> tab;
int n;
int counts[26];
const int one_code_length = 5;  // ceil(log_2(26))
// 1 int + 2500007 chars fits into the limit
// 1 int + 1 char + 25000070 bits doesn't fit
// 1 int + 1 char + 8 * 3100007 bits fits
void sset(char c, int pos) {
  counts[c-'a']++;
  if (pos >= MAXN){
    return;
  }
  pos *= one_code_length;
//  printf("Setting %c on %d\n", c, pos);
  c -= 'a';
  for(int i = 0; i < one_code_length; i++) {
    tab[pos + i] = (c % 2);
//    printf("setting tab[%d] = %d\n", pos+i, int(tab[pos+i]));
    c /= 2;
  }
}

char gget(int pos) {
  if (pos >= MAXN){
    return single;
  }
//  printf("Reading from pos %d\n", pos);
  pos*= one_code_length;
  short res = 0;
  for(int i = 0; i < one_code_length; i++) {
    res *= 2;
    if (tab[pos+one_code_length - i -1] == 1){
      res++;
    }
//    printf("tab[%d] = %d\n", pos + i, tab[pos +one_code_length -1- i]);
//    printf("res %d\n", res);
  }
//  printf("Result %c\n", 'a' + res);
  return 'a' + res;
}

int main() {
  scanf("%d", &n);
  if (n == 0) {
    while(scanf(" %c", &single) != EOF) {
      sset(single, n);
      n++;
    }
    for(int i = 0; i < n/2; i++){
      if (gget((n+1)/2 + i) != gget(n/2 - 1 - i)){
        printf("NIE\n");
        return 0;
      }
    }
    printf("TAK\n");
    return 0;
  }
  for(int i=0; i < n/2; i++) {
    scanf(" %c", &single);
    sset(single, i);
  }
  if ((n % 2) == 1){
    scanf(" %c", &single);
  }
  for(int i=0; i < n/2; i++){
    scanf(" %c", &single);
    counts[single - 'a']--;
    if (single != gget(n/2 - 1 - i)){
//      printf("letter %d doesnt match, is %c should be %c\n", n/2 - 1 - i, gget(n/2 - 1 -i), single);
      printf("NIE\n");
      return 0;
    }
  }
  for(int i=0; i < 26; i++){
    if (counts[i] != 0){
//      printf("Count %d doesn't match", i);
      printf("NIE\n");
      return 0;
    }
  }
  printf("TAK\n");
}