Description

Modern people are becoming increasingly interested in their family lineage. Given sufficient parent-child relationships, your task is to write a program to find the earliest ancestor of a specified individual.

Input Format

The input consists of multiple lines. First, there is a series of parent-child relationship descriptions, where each parent-child relationship is represented by two lines:

• A line starting with #name describes the father's name in a parent-child relationship.
• A line starting with +name describes the son's name in a parent-child relationship.

Following these, lines starting with ?name indicate a request to find the earliest ancestor of the specified person.
The input ends with a single $ to denote the end of the file.

It is specified that:

• Each person's name consists of exactly 6 characters.
• The first letter of each name is uppercase.
• No two individuals share the same name.
• There are at most 1000 parent-child relationships.
• The total number of individuals may reach up to 50,000.
• The family tree records do not exceed 30 generations.

Output Format

For each request to find an ancestor, output the result in the following format:
[person's name] [ancestor's name] followed by a newline.
The output should follow the order of the requests in the input.

#George
+Rodney
#Arthur
+Gareth
+Walter
#Gareth
+Edward
?Edward
?Walter
?Rodney
?Arthur
$

Edward Arthur
Walter Arthur
Rodney George
Arthur Arthur