Secret Decoder

You are given a set of keys and a list of messages. Each key consists of two strings: a target substring and its replacement. Your task is to decode each message by replacing every occurrence of the target substring in the message with the replacement string. The replacements are applied in the order they are given.

Note: The replacement of keys is independent, meaning that once a substring is replaced, it will not be processed again for further substitutions.

The problem can be formally described using the following formula:

\(\text{decoded u{message}} = f(\text{message}, keys)\)

where function \(f\) applies each replacement in the order provided.

inputFormat

The input is read from standard input (stdin) and has the following format:

<n>
<a₁> <b₁>
<a₂> <b₂>
... 
<aₙ> <bₙ>
<m>
<message₁>
<message₂>
...
<messageₘ>

Where:

• n is an integer representing the number of key pairs.
• Each of the next n lines contains two strings a and b separated by space, where all occurrences of a in a message will be replaced by b.
• m is an integer representing the number of messages.
• Each of the next m lines is a message that needs to be decoded.

outputFormat

The output is written to standard output (stdout) and consists of m lines. Each line is the decoded message corresponding to the input messages.

## sample

1
hello hi
1
hello

hi

</p>