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
#include <iostream>
#include <random>
#include <vector>
using namespace std;
//random_device rd;
mt19937 mt;
int r(int a, int b){
	return uniform_int_distribution<int>(a,b)(mt);
}

int bigPrimes[45] = {999999391, 999999433, 999999487, 999999491, 999999503, 999999527, 999999541, 999999587, 999999599, 999999607, 999999613, 999999667, 999999677, 999999733, 999999739, 999999751, 999999757, 999999761, 999999797, 999999883, 999999893, 999999929, 999999937, 1000000007, 1000000009, 1000000021, 1000000033, 1000000087, 1000000093, 1000000097, 1000000103, 1000000123, 1000000181, 1000000207, 1000000223, 1000000241, 1000000271, 1000000289, 1000000297, 1000000321, 1000000349, 1000000363, 1000000403, 1000000409, 1000000411};
int smallPrimes[25] = {41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157};

struct hasher{
	unsigned long long Fhash, Bhash, act_mult;
	int base, mod;

	hasher(){}
	hasher(int b, int m):Fhash(0),Bhash(0),act_mult(1),base(b),mod(m){}
	void add_char(char x){
		Fhash = (Fhash+act_mult*x)%mod;
		Bhash = (Bhash*base+x)%mod;
		act_mult = (act_mult*base)%mod;
	}
	bool same(){
		return Fhash==Bhash;
	}
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	vector<hasher>Hasze(4);
	for(hasher& h : Hasze)
		h = hasher(smallPrimes[r(0,24)], bigPrimes[r(0,44)]);

	cin >> ws;
	while(true){
		char c = cin.get();
		if(c==char_traits<char>::eof() || c < 'a')
			break;

		for(hasher& h : Hasze)
			h.add_char(c);

/*
		cerr << "after " << c << ":\n";
		for(hasher& h : Hasze)
			if(h.same())
				cerr << "Alert" << endl;
*/
	}

	for(hasher& h : Hasze)
		if(!h.same()){
			cout << "NIE\n";
			return 0;
		}

	cout << "TAK\n";
	return 0;
}