ls

Interview

Time limit1sMemory limit128 MB

Summary

Given a wildcard pattern where * matches any run of characters, print the input file names that match it, keeping input order.

Level: Medium5 of 10
Topics: Dynamic programming, String, Brute force, Recursion
Solved: No attempts yet

Problem

Hyunjin is building a hobby operating system at home. Today it is time to implement ls, the command that lists the files inside a directory. Hyunjin wants users to be able to pick out only the file names that match a pattern by using the wildcard *.

The wildcard * matches zero or more of any character. Every other character in the pattern (lowercase letters and .) must match itself exactly.

Input

The first line contains a pattern P. P has a length between 1 and 100 characters and consists only of lowercase letters, ., and *.

The second line contains N, the number of files in the directory ( $1 \le N \le 100$ ).

Each of the next N lines contains one file name. Each file name has a length between 1 and 100 characters and consists only of lowercase letters and ..

Output

Print the names of the files that match pattern P, one per line, in the order they appear in the input. If no file matches, print nothing.

Examples2

Example 1

Input

*.*
4
main.c
a.out
readme
yacc

Expected output

main.c
a.out

Example 2

Input

*a*a*a
4
aaa
aaaaa
aaaaax
abababa

Expected output

aaa
aaaaa
abababa