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
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
#define MAX 600000
#define XD 150000
#define MOD 1000000009

long long one = 1;

int pow( int a, int b )
{
	if ( b == 0 ) return 1;
	if ( b == 1 ) return a;

	if ( b % 2 ) return ( one * a * pow( a, b-1 ) ) % MOD;
	else return ( pow( (a*a)%MOD, b/2 ) );
}

int main()
{
	int n;
	char c;

	scanf( "%d%c", &n, &c );
	if ( n )
	{
		vector < int > f[4];
		for ( int i = 0; i < 4; ++i ) f[i].resize( XD );

		for ( int i = 0; i < n/2; ++i )
		{
			scanf( "%c", &c );
			c -= '0';

			f[0][i/XD] = ( f[0][i/XD] + c*pow( 29, i%XD ) ) % MOD;
			f[1][i%XD] = ( f[1][i%XD] + c*pow( 31, i/XD ) ) % MOD;
		}
		if ( n % 2 ) scanf( "%c", &c );
		for ( int i = n/2-1; i >= 0; --i )
		{
			scanf( "%c", &c );
			c -= '0';

			f[2][i/XD] = ( f[2][i/XD] + c*pow( 29, i%XD ) ) % MOD;
			f[3][i%XD] = ( f[3][i%XD] + c*pow( 31, i/XD ) ) % MOD;
		}

		bool flag = true;
		for ( int i = 0; i < XD; ++i )
		{
			if ( f[0][i] != f[2][i] || f[1][i] != f[3][i] )
			{
				flag = false;
				break;
			}
		}
		if ( flag ) printf( "TAK\n" );
		else printf( "NIE\n" );
	}
	else
	{
		vector < char > v;
		queue < char > q;
		for ( int i = 0; ; ++i )
        {
            if ( scanf( "%c", &c ) == EOF || c == '\n' ) break;
            if ( i < 2*MAX ) v.push_back( c );
            else q.pop();
            q.push( c );
            n++;
        }

        while ( v.size() > n/2 )
        {
            v.pop_back();
            q.pop();
        }

        bool flag = true;
        for ( int i = v.size()-1; i >= 0; --i )
        {
            if ( v[i] != q.front() )
            {
                flag = false;
                break;
            }
            q.pop();
        }

        if ( flag ) printf( "TAK\n" );
        else printf( "NIE\n" );
	}
}