Description

给定一系列父子关系，求某些人的祖先。“祖先”指的是从该人开始，沿父子关系向上追溯可以达到的辈分最大的人。

Format

Input

每行包含一个人名和一个标识符。标识符紧贴在名字的前面，不同标识符的含义如下：（人名用Name指代）
#Name：从下一行开始，每一个以标识符+开头的人名都是Name的儿子，直至遇到第一个不以+开头的人名；
+Name：上一个用#标识的人的儿子；
?Name：要求输出Name的祖先。
最后一行用一个字符$表示输入结束。

Output

按照输入文件的要求顺序，求出每一个用?标识的人的祖先，格式：本人的名字+一个空格+祖先的名字+回车。

Sample 1

Input

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

Output

Edward Arthur
Walter Arthur
Rodney George
Arthur Arthur

Limitation

2s, 131072KiB for each test case.

Hint

输入文件的总行数≤200,000。

Source

高一年级信息学奥赛模拟考(二)