[AdditionalFile5588.zip](file://AdditionalFile5588.zip?type=additional_file)

#5588. 「PA 2017 Final」Klawiatura

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

题目译自 PA 2017 Final Klawiatura

字节国的著名程序员 Bajtosz 键盘上的 Backspace 键坏了。他非常需要这个键，因为他粗心大意，经常在变量名中打错字，必须用这个倒霉的键来修正。然而，Bajtosz 认为 CapsLock 键是多余的。毕竟，要输入大写字母，按住 Shift 就够了。因此，他在自己的操作系统中，将 CapsLock 键和 Backspace 键的功能互换了。从那一刻起，他开始用 CapsLock 键来删除最后一个输入的字符。

Bajtosz 的麻烦还没完。一个狡猾的黑客需要窃取 Bajtosz 的密码。他成功地截获了键盘发出的信号。Bajtosz 没有意识到危险，用键盘敲出了他的密码。黑客正等着这一刻。他已经打开了一个编辑器，Bajtosz 在键盘上输入的所有内容都被记录了下来。

Bajtosz 在输入密码时，只使用了英文的大小写字母以及 CapsLock 键。在输入密码的过程中，CapsLock 键在 Bajtosz 的电脑上会删除最后一个输入的字母。特别地，当没有字母可以删除时，他不会按这个键。

然而，在黑客的编辑器里，没有任何字母被删除。每当 Bajtosz 按下 CapsLock 键，只是改变了输入模式。在奇数次按下 CapsLock 键后，Bajtosz 输入的每个小写字母都会变成大写，每个大写字母都会变成小写。在偶数次按下 CapsLock 键后，键盘的行为恢复正常。

举个样例，如果 Bajtosz 依次按下：P、CapsLock、t、A、CapsLock、a、k，那么他在自己的电脑上输入的字符串是 tak，而在黑客的编辑器中出现的字符串是 PTaak。

黑客在他的编辑器里看到了单词 s。请编写一个程序，对于 $n$ 个常见的密码 $z_1, z_2, \ldots, z_n$ 中的每一个，判断它是否可能是 Bajtosz 的密码。

输入格式

输入的第一行包含字符串 $s$ $(1 \le |s| \le 1000000)$，即出现在黑客编辑器中的单词。

第二行包含一个整数 $n$ $(1 \le n \le 1000000)$，表示需要检查的常见密码数量。

接下来的 $n$ 行每行包含一个非空的密码 $z_i$。所有单词 $z_i$ 的总长度不超过 $1000000$。

输入中的所有单词都只由大小写英文字母组成。

输出格式

输出应包含 $n$ 行；第 $i$ 行应包含 TAK 或 NIE，表示单词 $z_i$ 是否可能是 Bajtosz 的密码。

样例

输入

PTaak
4
PA
tak
ptak
nie

输出

TAK
TAK
NIE
NIE