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

using hash_t = unsigned long long;

struct hash_data {
	hash_data(hash_t m) : m(m) {}
	const hash_t m;
	hash_t h = 0;
	hash_t r = 0;
	hash_t p = 1;
};

int main() {
	constexpr char answer[2][3] = {
		{'N', 'I', 'E'},
		{'T', 'A', 'K'},
	};
	while (std::getchar() >= '0');
	hash_data hashes[] {
		8999uLL,
		100003uLL,
		1300843uLL,
		179426141uLL,
		180000017uLL,
	};
	for (char c; (c = std::getchar()) >= 'a';) {
		for (auto&& hash : hashes) {
			hash.h *= hash.m;
			hash.h += c;
			hash.r += c * hash.p;
			hash.p *= hash.m;
		}
	}
	bool ok = true;
	for (const auto& hash : hashes) {
		ok &= hash.h == hash.r;
	}
	for (char c : answer[ok]) {
		std::putchar(c);
	}
}