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.
Sample input:
<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!