Smart Password Validation

Time limit1sMemory limit2048 MB

Summary

For each attempt, decide whether it matches the password after at most one hand-shift, extra, or missing character error, with CAPS LOCK optionally on.

Level: Medium4 of 10
Topics: Implementation, String, Simulation
Solved: No attempts yet

Problem

People often make errors when entering passwords for one of their many accounts. This is becoming more of a problem with the rather lengthy passwords that many online portals require, since the more characters a password has, the greater the chance of a typing mistake.

Touch typists are prone to serious errors if one of their hands is not in the proper home row position, because they do not look at the keyboard while typing. Then every character typed by the misplaced hand is "one key off". For example, on a QWERTY keyboard, "lion" might become "kuib" if the right hand sits one key to the left of its normal home position.

The Frobozz Magic Security Company has decided to implement a new password validation algorithm that accounts for some common mistakes (but not all) made when entering passwords on a QWERTY-style keyboard.

Figure M.1: QWERTY keyboard

CAPS LOCK affects only alphabetic characters, and it toggles the effect of the shift key on those characters. When CAPS LOCK is off, letters are typed in lowercase unless one or both shift keys are pressed. When CAPS LOCK is on, letters are typed in uppercase unless a shift key is pressed, which produces lowercase. The algorithm assumes that the CAPS LOCK state does not change while a password is being entered.

The algorithm looks for deviations from the correct keystroke sequence. For example, if the correct password is ALg*, the correct sequence on the keyboard above is SHIFT-A, SHIFT-L, G, SHIFT-8. If the user accidentally presses CAPS LOCK before entering the password but then uses the correct sequence, they type alG*. If a touch typist moves the fingers of the left hand one space to the right of the correct position, makes no other errors, and follows the correct sequence without noticing the shift, they type SLh*. If CAPS LOCK is also accidentally on, they type slH*. Finally, a user might accidentally insert or delete a character. For example, ALg* might be mistyped as AL* or ALLg*.

Name	Acronym	Description	Examples
Left side off by one	LS	All characters on the left side of the keyboard are shifted right by one key. The left-shift key shifted right by one key is still the left-shift key.	`FlatHead` $\Rightarrow$ `GlsyHrsf`
Right side off by one	RS	All characters on the right side of the keyboard are shifted left by one key. The right-shift key shifted left by one key is still the right-shift key.	`FlatHead` $\Rightarrow$ `FkatGead`
Single extra character	EC	The entered password has an extra character	`Zorkmid` $\Rightarrow$ `Zorkmiid` (extra `i`)
Single missing character	MC	The entered password is missing a character.	`FCD#3` $\Rightarrow$ `FCD3` (missing the `#`)
CAPS LOCK was in effect by mistake	CL	All lowercase letters appear as uppercase and all uppercase letters appear as lowercase	`WE do it!` $\Rightarrow$ `we DO IT!`

Figure M.2: Permitted Error Types

At most one of the LS, RS, EC, and MC errors is permitted, but any of these may occur together with a CL error.

Input

The first line contains a string $p$ , the correct password ( $2 \leq \textrm{length}(p) \leq 24$ ). The second line contains a single positive integer $n$ ( $1 \leq n \leq 1\,000$ ), the number of lines that follow. Each of the following $n$ lines contains a single password to test, $t_i$ , where $\textrm{length}(p)-1 \leq \textrm{length}(t_i) \leq \textrm{length}(p)+1$ . The characters of all passwords come only from those on the QWERTY keyboard picture above, plus lowercase letters.

Output

Output $n$ lines. For each $t_i$ , print YES if $t_i$ matches $p$ under Frobozz's algorithm, and NO if it does not.

Examples1

Example 1

Input

Password=`A:'
9
Password=`A:'
pASSWORD=`a:'
Psddeotf=1S:'
oASSWIRD-`al;
Password=`A:'x
pASWORD=`a:'
pASSWORD=`a:'X
Osddeitf-1SL;
Psdeotf=1S:'

Expected output

YES
YES
YES
YES
YES
YES
YES
NO
NO