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
#include <iostream>
#include <string>
#include <unordered_map>
#include <deque>

using namespace std;

int getPali(int i) {
	return (i % 100) * 10000 + ((i / 100) % 100) * 100 + ((i / 10000) % 100);
}

int hasz(char c1, char c2, char c3)
{
	return (c1 - 'a') * 10000 + (c2 - 'a') * 100 + c3 - 'a';
}

int hasz(const std::deque<char>& d) 
{
	return hasz(d[0], d[1], d[2]);
}

struct info {
	int count;
	int first_seen;
	int last_seen;
};

int main()
{
	unordered_map<int, info> mapka;
	for (char c1 = 'a'; c1 <= 'z'; c1++) 
		for (char c2 = 'a'; c2 <= 'z'; c2++) 
			for (char c3 = 'a'; c3 <= 'z'; c3++) 
				mapka[hasz(c1, c2, c3)] = {0, -1, -1};
	
	char c;
	std::deque<char> current;
	std::deque<char> buffer_front;
	std::deque<char> buffer_rear;

	int num = 0;
	int limit = 1500000;
	int dupa;
	cin >> dupa;
	
	bool w = false;

	while (cin.get(c)) 
	{
		if (c == '\n' and !w) {
			w = true; continue;
		}
		if (c == '\n' and w) break;

		current.push_back(c);
		
		buffer_rear.push_back(c);
		if (num < limit) 
			buffer_front.push_back(c);
		else 
			buffer_rear.pop_front();
			
		if (current.size() == 3)
		{
			mapka[hasz(current)].count++;
			if (mapka[hasz(current)].first_seen < 0) 
				mapka[hasz(current)].first_seen = num;
			mapka[hasz(current)].last_seen = num;
			current.pop_front();
		} 
		num++;
	}

	limit = num < limit ? num : limit;

	for (int i = 0; i < limit; ++i) 
		if (buffer_front[i] != buffer_rear[limit - i - 1]) 
		{ 
			cout << "NIE";
			return 0;
		}
	
	for (auto x : mapka) {
		if (x.second.count) 
		{
			if (mapka[getPali(x.first)].count == x.second.count) 
			{
				if (x.second.first_seen - 2 != num - mapka[getPali(x.first)].last_seen - 1)
				{
					cout << getPali(x.first) << " " << x.second.last_seen << "\n"; 
					cout << "NIE";
					return 0;
				}
			} 
			else
			{
				cout << "NIE";
				return 0;
			}
		}
	}
	cout << "TAK";
	return 0;
}