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
100
#include <cstdio>
//#include <cassert>

//#define BUF (1024*812)
#define BUF 833334

#define C0 (1)
#define C1 (C0*26)
#define C2 (C1*26)
#define C3 (C2*26)
#define C4 (C3*26)
#define C5 (C4*26)
#define C6 (C5*26)
#define NLIM (20000000)

#define Q 1845589297LL
#define D C1


typedef unsigned ui;


#define CHBUF(ind,pos,elem) bufc[ind] = ((bufc[ind] / c[pos+1] ) * c[pos+1] + c[pos] * (elem) + bufc[ind] % c[pos] )
#define RAWBUF(ind,pos) ((bufc[ind] / c[pos]) % C1 )
#define RECALC(rpos) ((kon+(BUF*6)-(l-(rpos)))%(BUF*6))
#define GETBUF(rpos) (char)(((rpos)<l && (rpos+1)+(BUF*6)>l)?RAWBUF(RECALC(rpos)/6,RECALC(rpos)%6):100)

//char GETBUF(ui rpos){
//   return (((rpos)<l && (rpos+1)+(BUF*6)>l)?RAWBUF(RECALC(rpos)/6,RECALC(rpos)%6):100);
//}

int main(){
const int c[7] = {C0,C1,C2,C3,C4,C5,C6};
char a,adc=0;//wczytywana
ui n,k=0;//liczba wczytanych
ui bufc[BUF] = { 0 }, poc=0, kon=0, l=0;
unsigned long long lewy, prawy, H = 1;
const char tnie[] = "NIE";
   scanf(" %d",&n);
   while(scanf(" %c",&a) != 0){
      if(a > 'z' || a < 'a'){
         break;
      }
      a-='a';
      adc ^= a;
      if(k<NLIM/2){//TODO:sprawdzic warunek
         CHBUF(kon/6,kon%6,a);
         kon++;
         kon = kon % (6*BUF);
         l++;
      }
      //RabinKarp rolling hash
      if(k==0){
         lewy = a;
         prawy = a;
      }else{
         //fprintf(stderr,"PROC: k=%d a=%c ",k,char(a)+'a');
         if(k%2 == 0){
            H *= D;
            H = H % Q;
            //fprintf(stderr," lewy +=%c prawy+=%c",GETBUF(k/2)+'a',char(a)+'a');
            lewy = (lewy + H*GETBUF(k/2)) % Q;
            prawy = (D*prawy + a) % Q;
         }else{
            //fprintf(stderr,"prawy +=%c prawy-=%c",char(a)+'a',GETBUF(k/2)+'a');
            prawy = D*(Q*D + prawy - H*GETBUF(k/2)) % Q + a;
            prawy %= Q;
         }
         //fprintf(stderr,"\t%llu %llu H= %llu\n",lewy,prawy,H);
      }
      k++;
   }
   if(prawy == lewy){
      if(k%2 == 0){
         if(adc!=0){
            puts(tnie);
            return 0;
         }
      }else{
         if(adc!=GETBUF(k/2)){
            puts(tnie);
            return 0;
         }
      }
      for(int i=0;i<k/2;i++){
         char c1 = GETBUF(i);
         char c2 = GETBUF(k-i-1);
         if(c1 != 100 && c2 != 100 && c2 != c1){
            puts(tnie);
            return 0;
         }
      }
      puts("TAK");
   }else{
      puts(tnie);
   }
   //for(int i=0;i<k;i++){
   //   printf("%c", (char)GETBUF(i)+'a');
   //}
}