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 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
keyconsists of lowercase letters, digits, and underscores, 1 to 30 characters