Find a match, any match. You will be given very simple patterns. But, how fast can you come up with a solution when you are not allowed to use your regexp library? And yes, you might find this in your next interview.

# Problem

Input. A set of words and a set of patterns. Each word and each pattern is given in a line by itself. Words and patterns are separated by character #. In patterns, the character period . matches any character. The input is terminated by EOF.

Output. For each pattern, write in a single line the pattern, a space, and true if the pattern matches a word or false if it does not. Output patterns in the order you read them.

Input

Output

# Solution

Have you heard about tries? Use them maybe?

Here is a Ruby implementation.