Text Formalization

Jimmy has to make text more formal. This includes expanding contractions and, for some acronyms, writing the full name the first time the acronym appears.

An English contraction is a word or phrase made by shortening or combining parts of a longer phrase. For example, "don't" is a contraction of "do not", and "o'clock" comes from "of the clock".

An acronym is a string of letters or a word formed from the initial letters or parts of several words. For example, "ACM" abbreviates "Association for Computing Machinery", and "radar" comes from "radio detecting and ranging".

Given a list of contractions, a list of acronyms, and several texts, expand every contraction and expand only the first occurrence of each acronym within each text.

The first line contains two integers C < 50 and A < 50. C is the number of contractions to expand, and A is the number of acronyms to handle.

The next C lines list contractions and their formal expansions. The following A lines list acronyms and their expansions, one per line. Both lists use this format:

"contraction or acronym" -> "expansion"

Contractions, acronyms, and expansions may contain spaces, so both sides are enclosed in quotation marks. Each string is at most 80 characters long.

After the lists, the input contains the texts to expand. Each text consists of lines of at most 80 characters. No contraction or acronym is split across lines. A text ends with a line containing only the character #.

Output each text exactly as it was given, except for the required expansions. Also print the terminating # line for each text.

Every contraction must be fully expanded. A contraction may appear exactly as listed, entirely in uppercase, or capitalized with its first letter uppercase and the rest as listed. The expansion must use the corresponding case rule. If more than one case rule matches, use the first matching rule in this order: as listed, uppercase, then capitalized.

Acronyms help readers identify names, so only the first occurrence of each acronym in each text is changed. An acronym occurrence must match case exactly. Replace it with the expansion, then one space, then the original acronym in parentheses.

If more than one contraction or acronym can be applied, use the one that starts earliest in the text. If multiple entries start at the same position, use the entry that appears earliest in the input lists.