著名立陶宛程序员 Bytherine 的键盘上，Backspace 键坏了。这个键对她来说非常重要，因为她经常粗心大意，在输入变量名时容易出错，必须使用这个键来纠正。另一方面，她认为 CapsLock 键几乎毫无用处。事实上，要输入大写字母，完全可以使用 Shift 键。因此，她将 CapsLock 和 Backspace 的功能进行了对调。从那以后，她一直使用 CapsLock 键来删除最近输入的字符。

但这并没有解决 Bytherine 的所有问题。一名狡猾的黑客一直试图窃取 Bytherine 的密码。他成功拦截了键盘发出的信号。毫无防备的 Bytherine 在键盘上输入了她的密码。这正是黑客一直在等待的机会。现在，他掌握了 Bytherine 在键盘上输入的所有内容。

Bytherine 在输入密码时，仅使用了英文字母（大小写）和 CapsLock 键。为了输入密码，每当她想要删除最后一个输入的字符时，她就会按下 CapsLock 键。特别地，当还没有输入任何字符时，她不会按下该键。

另一方面，在黑客的编辑器中，没有任何字符被删除。每当 Bytherine 按下 CapsLock 键时，只会改变书写模式。在第奇数次按下 CapsLock 键后，Bytherine 输入的每个小写字母都会变为大写字母，反之亦然。在第偶数次按下 CapsLock 键后，键盘的行为恢复正常。

例如，如果 Bytherine 按下的键序列为：P、CapsLock、t、A、CapsLock、a、k，她最终输入的密码是 tak，但黑客看到的单词是 PTaak。

黑客的编辑器显示了单词 $s$。你的任务是编写一个程序，对于给定的 $n$ 个常用密码 $z_1, z_2, \dots, z_n$，判断它们是否可能是 Bytherine 的密码。

输入格式

第一行包含一个字符串 $s$ ($1 \le |s| \le 1\,000\,000$)，即黑客编辑器中显示的单词。 第二行包含一个整数 $n$ ($1 \le n \le 1\,000\,000$)，即需要检查的常用密码数量。 接下来的 $n$ 行，第 $i$ 行包含一个非空密码 $z_i$。所有 $z_i$ 的长度之和不超过 $1\,000\,000$。输入中的所有单词仅由英文字母的大小写字母组成。

输出格式

输出 $n$ 行；第 $i$ 行应包含 YES 或 NO，表示 $z_i$ 是否可能是 Bytherine 的密码。

样例

输入 1

PTaak
4
PA
tak
ptak
nie

输出 1

YES
YES
NO
NO