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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
#include <cstdint>
#include <cstdio>
#include <memory>
#include <vector>
#include <deque>

using namespace std;


// two-way hasher
struct Hasher2w {
  virtual void append(char ch) = 0;
  virtual void prepend(char ch) = 0;
  virtual bool operator==(Hasher2w const &rhs) const = 0;
  bool operator!=(Hasher2w const &rhs) { return not (*this == rhs); }
  
  virtual shared_ptr<Hasher2w> clone() const = 0;
};


// counts occurrences
struct ByteHistogram: Hasher2w {
  vector<size_t> counter;
  
  ByteHistogram(): counter(256, 0) { }
  
  void append(char ch) {
    counter[(unsigned char)(ch)]++;
  }
  
  void prepend(char ch) {
    counter[(unsigned char)(ch)]++;
  }
  
  bool operator==(Hasher2w const &rhs) const {
    ByteHistogram const *rhstp = dynamic_cast<ByteHistogram const *>(&rhs);
    if(rhstp == nullptr) return false;
    return counter == rhstp->counter;
  }
  
  bool possiblePalindrome() const {
    size_t odds = 0;
    for(size_t i = 0; i < 256; i++) {
      if(counter[i] % 2 == 1) odds++;
      if(odds >= 2) return false;
    }
    return true;
  }
  
  virtual shared_ptr<Hasher2w> clone() const { return make_shared<ByteHistogram>(*this); }
};


// keeps prefix and suffix
struct SideKeeper: Hasher2w {
  size_t const length;
  deque<char> prefix;
  deque<char> suffix;
  
  SideKeeper(size_t _length): length(_length) { }
  
  void append(char ch) {
    suffix.push_back(ch);
    if(suffix.size() > length) suffix.pop_front();
    if(prefix.size() < length) prefix.push_back(ch);
  }
  
  void prepend(char ch) {
    prefix.push_front(ch);
    if(prefix.size() > length) prefix.pop_back();
    if(suffix.size() < length) suffix.push_front(ch);
  }
  
  bool operator==(Hasher2w const &rhs) const {
    SideKeeper const *rhstp = dynamic_cast<SideKeeper const *>(&rhs);
    if(rhstp == nullptr) return false;
    return prefix == rhstp->prefix and suffix == rhstp->suffix;
  }
  
  virtual shared_ptr<Hasher2w> clone() const { return make_shared<SideKeeper>(*this); }
};


// calculates radix-based multiple-digit number modulo dividend (you append/prepend the digits)
struct DigitalHasher2w: Hasher2w {
  uint32_t const dividend;
  uint32_t const radix;
  unsigned int degree;
  uint32_t powval;
  uint32_t state;
  
  DigitalHasher2w(uint32_t _dividend, uint32_t _radix): dividend(_dividend), radix(_radix), degree(0), powval(1), state(0) { }
  
  void append(char ch) {
    state = ((unsigned char)(ch) * uint64_t(powval) + state) % dividend;
    powval = (powval * uint64_t(radix)) % dividend;
    degree++;
  }
  
  void prepend(char ch) {
    state = (state * uint64_t(radix) + (unsigned char)(ch)) % dividend;
    powval = (powval * uint64_t(radix)) % dividend;
    degree++;
  }
  
  bool operator==(Hasher2w const &rhs) const {
    DigitalHasher2w const *rhstp = dynamic_cast<DigitalHasher2w const *>(&rhs);
    if(rhstp == nullptr) return false;
    return state == rhstp->state;
  }
  
  virtual shared_ptr<Hasher2w> clone() const { return make_shared<DigitalHasher2w>(*this); }
};


// calculates (1*a0 + 2*a1 + 3*a2 + ...) MOD dividend (you append/prepend elements of (a) sequence)
// keeps the value of (a0 + a1 + ...) MOD dividend and uses it in comparisons as well
struct LinearHasher2w: Hasher2w {
  uint32_t const dividend;
  uint32_t sum;
  uint32_t count;
  uint32_t state;
  
  LinearHasher2w(uint32_t _dividend): dividend(_dividend), sum(0), count(0), state(0) { }
  
  void append(char ch) {
    unsigned char t = ch;
    count++;
    state = (state + t * uint64_t(count)) % dividend;
    sum = (sum + uint64_t(t)) % dividend;
  }
  
  void prepend(char ch) {
    unsigned char t = ch;
    count++;
    state = (state + uint64_t(sum) + t) % dividend;
    sum = (sum + uint64_t(t)) % dividend;
  }
  
  bool operator==(Hasher2w const &rhs) const {
    LinearHasher2w const *rhstp = dynamic_cast<LinearHasher2w const *>(&rhs);
    if(rhstp == nullptr) return false;
    return state == rhstp->state and sum == rhstp->sum;
  }
  
  virtual shared_ptr<Hasher2w> clone() const { return make_shared<LinearHasher2w>(*this); }
};


// use multiple two-way hashers as one
struct MultiHasher2w: Hasher2w {
  vector< shared_ptr<Hasher2w> > hashers;
  
  MultiHasher2w(vector< shared_ptr<Hasher2w> > &_hashers): hashers(_hashers) { }
  
  MultiHasher2w(MultiHasher2w const &arg) {
    for(auto const &ptr: arg.hashers) {
      hashers.push_back(ptr->clone());
    }
  }
  
  void append(char ch) {
    for(size_t i = 0; i < hashers.size(); i++) hashers[i]->append(ch);
  }
  
  void prepend(char ch) {
    for(size_t i = 0; i < hashers.size(); i++) hashers[i]->prepend(ch);
  }
  
  bool operator==(Hasher2w const &rhs) const {
    MultiHasher2w const *rhstp = dynamic_cast<MultiHasher2w const *>(&rhs);
    if(rhstp == nullptr) return false;
    if(hashers.size() != rhstp->hashers.size()) return false;
    for(size_t i = 0; i < hashers.size(); i++) if(*(hashers[i]) != *(rhstp->hashers[i])) return false;
    return true;
  }
  
  virtual shared_ptr<Hasher2w> clone() const { return make_shared<MultiHasher2w>(*this); }
};


// wrapper for ignoring all the characters besides small latin letters
struct FilteredLLHasher2wWrapper: Hasher2w {
  shared_ptr<Hasher2w> ptr;
  FilteredLLHasher2wWrapper(Hasher2w &_hasher): ptr(&_hasher) { }
  FilteredLLHasher2wWrapper(shared_ptr<Hasher2w> const &_ptr): ptr(_ptr) { }
  
  FilteredLLHasher2wWrapper(FilteredLLHasher2wWrapper const &arg): ptr(arg.ptr->clone()) { }
  
  void append(char ch) {
    if(not ('a' <= ch and ch <= 'z')) return;
    ptr->append(ch);
  }
  
  void prepend(char ch) {
    if(not ('a' <= ch and ch <= 'z')) return;
    ptr->prepend(ch);
  }
  
  bool operator==(Hasher2w const &rhs) const {
    FilteredLLHasher2wWrapper const *rhstp = dynamic_cast<FilteredLLHasher2wWrapper const *>(&rhs);
    if(rhstp != nullptr) return *ptr == *(rhstp->ptr);
    return *ptr == rhs;
  }
  
  virtual shared_ptr<Hasher2w> clone() const { return make_shared<FilteredLLHasher2wWrapper>(*this); }
};


int main() {
  vector< shared_ptr<Hasher2w> > hashers;
  
  shared_ptr<ByteHistogram> hist = make_shared<ByteHistogram>();
  
  hashers.push_back(hist);
  hashers.push_back(make_shared<SideKeeper>(4096));
  hashers.push_back(make_shared<DigitalHasher2w>(1662389207, 1200099553));
  hashers.push_back(make_shared<DigitalHasher2w>(1630171901, 1214103271));
  hashers.push_back(make_shared<DigitalHasher2w>(1822084421, 1338144299));
  hashers.push_back(make_shared<DigitalHasher2w>(1107565939, 1030805731));
  hashers.push_back(make_shared<LinearHasher2w>(1755431533));
  hashers.push_back(make_shared<LinearHasher2w>(1631560141));
  hashers.push_back(make_shared<LinearHasher2w>(1759200251));
  hashers.push_back(make_shared<LinearHasher2w>(1941468271));
  
  FilteredLLHasher2wWrapper fh(make_shared<MultiHasher2w>(hashers));
  FilteredLLHasher2wWrapper rh(fh);
  
  for(int ch; (ch = getchar_unlocked()) != EOF;) {
    fh.append(ch);
    rh.prepend(ch);
  }
  
  if(hist->possiblePalindrome() and fh == rh) {
    puts("TAK");
  } else {
    puts("NIE");
  }
  
  return 0;
}