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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
/*
 *  Copyright (C) 2018  Paweł Widera
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details:
 *  http://www.gnu.org/licenses/gpl.html
 */
#include <iostream>
#include <bitset>
using namespace std;

// large primes < 2**32 / N
#define MOD1 165190957
#define MOD2 165191011
#define N 26
#define SHIFT 97
#define BITSIZE 21000000  // should be > 20M / 4 * 5bits
#define MAX_LENGTH 20000000

bitset<BITSIZE> data(0);
int first = 0;
int last = 0;


void bits_pop() {
	first = (first + 5) % BITSIZE;
}


void bits_push(char value) {
	bitset<5> bits(value);
	for (int i = 0; i < 5; ++i) {
		data[last++] = bits[i];
	}
	last = last % BITSIZE;
}


char bits_get() {
	char value = 0;
	for (int i = 0; i < 5; ++i) {
		value += data[first + i] << i;
	}
	return value;
}


int main() {
	char letter, next_letter, front;

	unsigned int n;
	cin >> n;
	if (n == 0) {
		n = MAX_LENGTH;
	}

	unsigned int i = 0;
	cin >> letter;
	if (cin >> next_letter) {
		++i;
	}
	if (i == 0) {
		cout << "TAK" << endl;
		return 0;
	}

	long long int power1 = 1;
	long long int h1_reverse = letter - SHIFT;
	long long int h1_forward = next_letter - SHIFT;

	long long int power2 = 1;
	long long int h2_reverse = letter - SHIFT;
	long long int h2_forward = next_letter - SHIFT;

	bits_push(next_letter - SHIFT);

	while (cin >> letter) {
		letter -= SHIFT;
		front = bits_get();

		if (++i % 2 == 0) {
			// remove the oldest queued letter and add the current letter
			h1_forward = (N * (h1_forward - power1 * front) + letter) % MOD1;
			if (h1_forward < 0) h1_forward += MOD1;

			h2_forward = (N * (h2_forward - power2 * front) + letter) % MOD2;
			if (h2_forward < 0) h2_forward += MOD2;
		}
		else {
			power1 = (N * power1) % MOD1;
			power2 = (N * power2) % MOD2;
			// add current letter
			h1_forward = (N * h1_forward + letter) % MOD1;
			h2_forward = (N * h2_forward + letter) % MOD2;
			// add oldest queued letter
			h1_reverse = (h1_reverse + power1 * front) % MOD1;
			h2_reverse = (h2_reverse + power2 * front) % MOD2;

			// remove top element from the queue
			bits_pop();
		}

		if (i <= n / 2) {
			bits_push(letter);
		}
	}

	if (h1_forward == h1_reverse && h2_forward == h2_reverse) {
		cout << "TAK" << endl;
	} else {
		cout << "NIE" << endl;
	}
	return 0;
}