Pattern Matching

In computer science, pattern matching is the act of checking whether a sequence conforms to (matches) a given pattern. In this problem we express patterns over sequences of decimal digits using a small set of rules.

A pattern is a string of length at least one made up of decimal digits 0–9, asterisks *, and hash signs #.

• A digit matches exactly itself.
• * denotes an even number (0, 2, 4, …) of arbitrary digits.
• # denotes an odd number (1, 3, 5, …) of arbitrary digits.

For example, the pattern 129 matches only the sequence 129. The pattern 1*3 matches every sequence that begins with 1, ends with 3, and has an even number of digits between the first and last digit. As another example, the pattern #55 matches 155, 12355, and 1234555, but none of 55, 1255, or 123455.

Write a program that decides whether a given sequence matches a given pattern.

The input consists of one or more data sets. Each data set contains a single pattern and one or more sequences to match against it.

The first line of each data set is the pattern; each following line is a sequence to compare against that pattern. The end of every data set except the last is marked by the word END on its own line, and the end of the last data set is marked by the word QUIT on its own line.

Every line is at most 100,000 characters long.

For each sequence, print one line in the following format:

k.s. result

where k is the data set number (starting at 1), s is the sequence number within that data set (restarting at 1 for each data set), and result is match if the sequence matches the pattern and not otherwise.