Earliest Ancestor

Special for beginners, ^_^

Problem Description

Modern people are becoming more and more interested in their family lineage. Given plenty of father-child relationships, write a program to find the earliest ancestor of a certain person.

Input Format

The input consists of many lines. First comes a series of father-child relationships: each group consists of two lines — a line of the form #name gives the father's name in that father-son group, and a line of the form +name gives a son's name. Next come lines of the form ?name, asking for that person's earliest ancestor. Finally a single $ marks the end of the file. Every person's name has exactly 6 characters, starts with a capital letter, and no two people share a name. There may be at most 1000 father-child groups, at most 50000 people in total, and the family tree records no more than 30 generations.

Output Format

In the order of the input requests, find the ancestor of each person asked: output that person's name, a space, and the ancestor's name, followed by a newline.

Sample Input 1

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

Sample Output 1

Edward Arthur
Walter Arthur
Rodney George
Arthur Arthur

Constraints

1s, 1024KiB for each test case.