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
#include <algorithm>

using ull = unsigned long long;
using namespace std;
#ifdef _WIN32
inline int getchar_unlocked() { return getchar(); }
#endif

struct hashFunction
{
	const ull M;
	const ull p;
	ull leftRight = 0;
	ull rightLeft = 0;

	hashFunction(const ull _M, const ull _p) : M(_M), p(_p) {}

	ull currentPow = 1;
	inline void calcLeftRight(char c)
	{
		leftRight = (leftRight * p + c) % M;
	}

	inline void calcRightLeft(char c)
	{
		rightLeft = (c*currentPow + rightLeft) % M;
		currentPow = (currentPow * p) % M;
	}
};

bool isPalindrome()
{
	char c;
	hashFunction ha(3307657987ULL, 812ULL);
	//hashFunction hb(16351819937503439ULL, 838);
	hashFunction hc(2339142427ULL, 713ULL);

	while((c = getchar_unlocked()) != EOF)
	{
		if (c < 'a' || c > 'z') continue;
		c -= 'a';
		++c;

		ha.calcLeftRight(c);
		ha.calcRightLeft(c);

		//hb.calcLeftRight(c);
		//hb.calcRightLeft(c);

		hc.calcLeftRight(c);
		hc.calcRightLeft(c);
	}

	return ha.leftRight == ha.rightLeft && /*hb.leftRight == hb.rightLeft &&*/ hc.leftRight == hc.rightLeft;
}

int main()
{
	int n;
	scanf("%d", &n);
	printf("%s", isPalindrome() ? "TAK" : "NIE");
	return 0;
}