Stems Sell

The designers at Spark Plug Searching, Ltd. want to shrink the dictionary used by their new spell checker. Their idea is to store only the basic "stem" form of each word, dropping plurals, past tenses, and other grammatical variants.

When a word is pulled from a document and we want to spell-check it, we apply a series of rules that rewrite the word toward its likely stem form, then look that rewritten word up in the dictionary.

Natural language is messy, so finding a good rule set takes experimentation. The team designed a small language for rewrite rules. A rule has the form:

pattern => replacement

A pattern is a sequence of one or more characters, interpreted as follows:

• A lower-case letter matches a single occurrence of that same letter, in either upper or lower case. For example, the pattern ab matches ab, aB, Ab, or AB inside a word.
• An asterisk * matches one or more alphabetic characters. A pattern contains at most one asterisk, and if it is present it is the first character of the pattern.
• An upper-case V matches any vowel (a, e, i, o, or u).
• An upper-case C matches any consonant (any letter that is not a vowel).
• A digit 1-9 matches the same text that was matched by the pattern character at that position, counting the first character of the pattern as position 1. A digit k may appear in the pattern only after position k.

For example, the pattern *C2ies matches any word of at least 6 characters that ends in two copies of the same consonant followed by ies.

The replacement part of a rule uses a limited set of the same characters: lower-case letters, which are copied as-is, and digits, which are replaced by the same text they matched in the pattern. For example, the rule

*C2ies => 122y

applied to berries matches * against be, the C and the 2 each against r, and ies against ies. In the replacement, 1 is the text matched by * (be), each 2 is r, and y is copied as-is, so berries is rewritten to berry.

Write a program that reads a set of rewrite rules and applies them to the words of a paragraph. A word is a maximal run of consecutive alphabetic characters. A pattern must match the whole word. For each word, apply the rules one at a time, in the order given, until a pattern matches or the rules run out. If a pattern matches, rewrite the word with that rule and stop trying further rules; otherwise leave the word unchanged.

The input contains multiple data sets. Each data set begins with one or more rules, one per line, in the format described above, followed by an empty line. After that empty line come one or more lines of text. The text is terminated either by an empty line (when another data set follows) or by a line containing only the left-justified string ***, which marks the end of the input.

For each data set, print its lines of text with every word rewritten according to that data set's rules; leave all non-word characters unchanged. After the rewritten text of each data set, print a single line containing only the left-justified string ***.