Contract Clause Chain Expansion

A contract-assembly tool stores a library of named clauses. Each clause's text is a sequence of space-separated tokens, and a token is either a literal word or a reference to another clause written as {clause_name}, which must be replaced by that other clause's own fully resolved text wherever it appears. A master document is written the same way, mixing literal words with clause references. Clause references never form a cycle, and every clause name used as a reference is guaranteed to be defined in the library. Produce the fully expanded master document, with every reference — direct or nested — replaced all the way down to plain words.

Input format

Line 1: an integer n — the number of clause definitions. Next n lines: each line is "name text", where name is the clause's name and text is its token sequence (text may be empty, in which case the line contains only the name and nothing after it). Names are unique. Last line: the master document's token sequence (it may be empty, i.e. a blank line).

Output format

Print a single line: the fully expanded master document, with tokens separated by single spaces. If the expansion has zero tokens, print an empty line.

Constraints

• 1 <= n <= 1000
• Each clause name consists of lowercase English letters, digits, and underscores, starts with a letter, and has length 1-32; all n names are distinct.
• Every text (a clause's own text, or the master document) has at most 1000 tokens. Each token is either a literal word of 1-20 lowercase letters/digits, or a reference written as exactly {name}: an opening brace, a defined clause name, and a closing brace, with no other characters.
• The reference graph among clauses is acyclic, and every referenced name is one of the n defined clause names.
• For every clause, and for the master document, the number of tokens after full expansion does not exceed 200000.

3
liability {refund_policy} applies
refund_policy full refund within 30 days
warranty {liability} extended coverage
the {warranty} is standard

the full refund within 30 days applies extended coverage is standard

2
greeting hello there
farewell goodbye friend
{greeting} and {farewell}

hello there and goodbye friend