Look at professionally typeset text and you'll notice that certain letter combinations are more than just the concatenation of their parts. For instance, `f' followed by `i' should be rendered as a melded character (example: ) and not just an f followed by an i (example: ) These special combinations are called ligatures, and may be specified by a ligature table. Let's say that a text atom is either a non-whitespace character or a ligature. A ligature table is a set of substitutions, each specifying a pair of text atoms alpha and omega and a replacement text atom lambda. While scanning the input from left to right, if alpha is immediately followed by omega then lambda is substituted for both; atom lambda may be part of the source text for yet another substitution.
Your task is to write a program that reads a ligature table and then processes some text according that table.
Because our contest environment uses plain ASCII, a ligature is represented by a parentheses-delimited alphabetic string. For example, we represent the ligature for fi by the four-character ASCII string (fi).
Input: The input is a ligature table followed by text to be processed. A ligature table is a line of text consisting of the 10 character string <ligtable> (and a newline) followed by a sequence of substitution lines and terminated by a line of text consisting of the 11 character string </ligtable> (and a newline). Each substitution line consists of a pair of text atoms followed by a single space, followed by a replacement text atom, followed by a newline. All the substitutions in a table are consistent with each other.
Each input line is at most 100 characters long. No parentheses appear after the </ligtable> line.
Output: Process the text after the ligature table according to the rules in the ligature table. All spaces, tabs, and newlines should preserved, and none should be added.
<ligtable> ff (ff) fi (fi) fl (fl) (ff)i (ffi) (ff)l (ffl) </ligtable> Offline office floor furniture finally offered! Finally? Yeah, finally!
Corresponding sample output:
O(ffl)ine o(ffi)ce (fl)oor furniture (fi)nally o(ff)ered! Finally? Yeah, (fi)nally!