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
#include <cstdio>
#include <cstring>
#include <ctype.h>

//from https://sio2.mimuw.edu.pl/c/pa-2015-1/s/88254/source/
const int primeExponent = 61;
const unsigned long long prime = (1ULL << primeExponent) - 1ULL;
const unsigned long long hash1 = 1919222792405563639ULL;
const unsigned long long hash2 = 1940348388277362841ULL;

// Modulo prime.
class Mod {
 public:
  // x must be < p
  explicit Mod(unsigned long long x) : val{x} {}

  Mod operator+(Mod b) const {
    unsigned long long res = val + b.val;
    if (res >= prime) res -= prime;
    return Mod{res};
  }

  Mod operator*(Mod b) const {
    unsigned a0 = unsigned(val);
    unsigned a1 = unsigned(val >> 32);
    unsigned b0 = unsigned(b.val);
    unsigned b1 = unsigned(b.val >> 32);
    unsigned long long res0 = (unsigned long long)(a0) * (unsigned long long)(b0);
    unsigned long long res1 = (unsigned long long)(a0) * (unsigned long long)(b1) + (unsigned long long)(a1) * (unsigned long long)(b0);
    unsigned long long res2 = (unsigned long long)(a1) * (unsigned long long)(b1);
    unsigned long long res =
      (res0 & prime) + (res0 >> primeExponent) +
      ((res1 << 32) & prime) + (res1 >> (primeExponent - 32)) +
      ((res2 << (64 - primeExponent)) & prime) +
      (res2 >> (2 * primeExponent - 64));
    return Mod{res % prime};
  }

  bool operator==(Mod b) const { return val == b.val; }

 private:
  unsigned long long val;
};

int main() {
	int len;
	char tab[110];
	Mod b1(0), b2(0), e1(0), e2(0);
	Mod power1(1), power2(1);

	scanf("%d\n",&len);

	while (scanf("%100s",tab)==1 && strlen(tab)>0) {
		for (char *cptr=tab; *cptr; ++cptr) {
			b1 = b1*Mod(hash1) + Mod((int)*cptr);
			e1 = e1 + power1*Mod((int)*cptr);
			power1 = power1 * Mod(hash1);

			b2 = b2*Mod(hash2) + Mod((int)*cptr);
			e2 = e2 + power2*Mod((int)*cptr);
			power2 = power2 * Mod(hash2);
		}
	}

	if (b1==e1 && b2==e2) {
		printf("TAK\n");
	} else {
		printf("NIE\n");
	}

	return 0;
}