Keyboard

Time limit2sMemory limit512 MB

Summary

Given the hacker's recorded string and a candidate password, decide whether the candidate could produce that recording under the caps-lock/backspace swap.

Level: Medium6 of 10
Topics: String, Two pointers, Simulation, Implementation
Solved: No attempts yet

Problem

On the keyboard of Bytherine, the famous Lithuanian programmer, the Backspace key is broken.

This key matters a lot to her. She is sloppy and often misspells variable names, and every time she has to fix them with this ill-fated key. On the other hand, she considers CapsLock practically useless. To type a capital letter you can just press Shift, after all. So she swapped the functions of CapsLock and Backspace. Since then she presses CapsLock to delete the character she just typed. But that is not the end of Bytherine's troubles. A cunning hacker has been trying to steal her password. He intercepted the signal the keyboard emits. Unaware of the danger, Bytherine typed her password on the keyboard, which is exactly what the hacker was waiting for. Now he has everything she typed.

To type her password, Bytherine used only lowercase and uppercase English letters and the CapsLock key. Whenever she wanted to delete the last character she had entered, she pressed CapsLock. In particular, she did not press it when no character had been entered yet.

In the hacker's editor, on the other hand, no character was deleted. Every time Bytherine pressed CapsLock, only the writing mode changed. After every odd press of CapsLock, every lowercase letter she entered became an uppercase letter and vice versa. After every even press of CapsLock, the keyboard behaved normally again.

For example, if Bytherine pressed P, CapsLock, t, A, CapsLock, a, k in that order, she typed the word tak, but the hacker sees the word PTaak.

The hacker's editor displays the word $s$ . Write a program that, for each of $n$ popular passwords $z_1, z_2, \ldots, z_n$ , determines whether it can be Bytherine's password.

Input

The first line of the input contains the word $s$ displayed in the hacker's editor ( $1 \le |s| \le 1\,000\,000$ ).

The second line contains one integer $n$ , the number of popular passwords to check ( $1 \le n \le 1\,000\,000$ ).

The $i$ -th of the following $n$ lines contains exactly one password $z_i$ , which is non-empty. The sum of the lengths of the words $z_i$ does not exceed $1\,000\,000$ . All words in the input consist of only uppercase and lowercase English letters.

Output

Write $n$ lines. The $i$ -th line contains YES if Bytherine's password can be $z_i$ , and NO otherwise.

Examples1

Example 1
Input
```
PTaak
4
PA
tak
ptak
nie
```
Expected output
```
YES
YES
NO
NO
```