Start

2019-02-04 13:00 UTC

Kattis Set 04

End

2019-02-11 09:29 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -281 days 23:59:26

Time elapsed

164:29:59

Time remaining

0:00:00

Problem G
Dictionary Attack

In choosing a password, it’s important to avoid dictionary words or simple variants of them. Using a password based on a dictionary word makes it easier for an attacker to break into your account by simply guessing dictionary words and similar strings.

We say that a password is unacceptable if it can be obtained by making three or fewer elementary changes to a dictionary word. An elementary change can be either of the following.

  • Replace any one character with a decimal digit.

  • Transpose any two adjacent characters.

Input

Input begins with a positive integer $N \leq 1\, 000$ and a list of $N$ dictionary words, one per line. After this list is a sequence of up to $250$ password candidates, one per line up to the end of file. The list of dictionary words use only uppercase and lowercase letters (a–z), and the password candidates use only uppercase and lowercase letters (a–z) and decimal digits $0$$9$. Each dictionary word and password candidate is at most $15$ characters long.

Output

From the list of password candidates, print out a list of just the acceptable passwords in the same order, one per line.

Sample Input 1 Sample Output 1
5
book
apple
secret
December
vertigo
book
b00k
alppe
a1ppe
secret
esrcte
erscte
vreitg0
arithmetic
D3c3m63r
d3c3mb3r
ap1p3
erscte
arithmetic
D3c3m63r
d3c3mb3r