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
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <string>
#include <unordered_map>
#include <queue>

using namespace std;

const int MAX_SIZE = 250 * 1000;

bool isPalindrome(string str)
{
	for (unsigned i = 0; i < str.size() / 2; ++i)
	{
		if (str[i] != str[str.size() - i - 1])
		{
			return false;
		}
	}

	return true;
}

bool isPalindromePartial()
{
	unordered_map<char, int> charCount;
	unordered_map<int, int> doubleCharCount;

	int len = 0;
	char prev = 1;
	string begStr;
	queue<char> endStr;
	for(char c = 'a'; cin >> c && c >= 'a'; ++len)
	{
		if(prev != 1)
			doubleCharCount[c * 1000 + prev] += 1;
		charCount[c] += 1;

		if (len < MAX_SIZE)
		{
			begStr += c;
		}
		else 
		{
			endStr.push(c);
			if (endStr.size() > MAX_SIZE)
				endStr.pop();
		}

		prev = c;
	}


	// we can do it
	if (len == begStr.size() + endStr.size()) 
	{
		while (!endStr.empty())
		{
			begStr += endStr.front();
			endStr.pop();
		}
		return isPalindrome(begStr);
	}


	// compare endings
	for (int i = endStr.size() - 1 ; i >= 0 ; --i)
	{
		if (begStr[i] != endStr.front())
			return false;
		endStr.pop();
	}


	// parity of letters
	int oddNum = 0;
	for (auto pair : charCount)
	{
		if (pair.second % 2 == 1)
		{
			++oddNum;
			if (oddNum > 1)
				return false;
		}
	}

	if (len % 2 == 1 && oddNum > 0)
		return false;


	// parity of pairs of letters
	oddNum = 0;
	for (auto pair : doubleCharCount)
	{
		int reverse = 1000 * (pair.first % 1000) + pair.first / 1000;
		if (doubleCharCount.count(reverse) == 0 || doubleCharCount[reverse] != pair.second)
		{
			++oddNum;
			if (oddNum > 1)
				return false;
		}
	}

	if (len % 2 == 0 && oddNum > 0)
		return false;

	return true;
}

int main()
{
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	bool palin;
	if (N > 0 && N < 2 * MAX_SIZE)
	{
		string str;
		cin >> str;
		palin = isPalindrome(str);
	}
	else 
	{
		palin = isPalindromePartial();
	}

	if(palin)
		cout << "TAK" << endl;
	else
		cout << "NIE" << endl;

	return 0;
}