Taco String Replacement

You are given a series of replacement rules and a list of query strings. For each query string, you must apply the replacement rules sequentially in the given order. Each replacement rule consists of a target substring and its replacement string. When processing a query string, every occurrence (non-overlapping and from left to right) of the target substring is replaced by its corresponding replacement.

Note: Even if a replacement introduces new occurrences of a pattern from an earlier rule, those are not processed again. The rules are applied exactly once per query in order.

For example, if the replacement rules are:

• ("abc", "xy")
• ("bc", "yz")
• ("a", "x")

and the query string is "abcde", then applying the rules in order yields "xyde".

inputFormat

The input is given via standard input (stdin). The first line contains two integers R and Q, where R is the number of replacement rules and Q is the number of query strings. The following R lines each contain two strings separated by a space: the first is the substring to be replaced and the second is its replacement (an empty replacement is allowed). The next Q lines each contain a query string which must be processed using the provided rules.

outputFormat

For each query string, output a single line representing the string after all the replacement rules have been applied.## sample

1 1
a b
abc

bbc