You are given a template string T on a single line, which may contain zero or more placeholders of the exact form {{name}}, where name is one or more characters from lowercase letters, digits, and underscores. You are also given n definition lines, each of the exact form key=value (the value may contain any characters except a newline, including = itself — always split a definition line on only its FIRST =).

Replace every well-formed placeholder {{name}} in T with the value defined for that name. If name has no definition, leave that placeholder exactly as-is (including its braces) in the output. If the same key is defined more than once, the LAST definition for that key wins. A {{ that is not followed later by a matching name and }} forming a well-formed placeholder (for example {{}} with an empty name, or a stray unmatched {{) is left completely untouched as ordinary text. Substituted values are inserted literally — they are never themselves re-scanned for placeholders.

Input format

Line 1: the template T (may be empty). Line 2: an integer n. Lines 3..n+2: each a definition key=value.

Output format

T with all well-formed, defined placeholders substituted, on one line.

Constraints

• 0 ≤ length of T ≤ 300
• 0 ≤ n ≤ 50
• each key consists of lowercase letters, digits, and underscores, 1 to 30 characters

Hello, {{name}}!
1
name=World

Hello, World!

{{a}}-{{b}}
1
a=1

1-{{b}}