题目描述

给定一些父子关系，请找出被询问者在家谱中能够追溯到的最早祖先。如果一个人没有已知的父亲，则将他本人作为最早祖先。

每个人的姓名不同，家谱中不存在循环，一个人至多有一个父亲。

输入格式

输入由若干行组成：

• #name：开始一组记录，指定这一组中的父亲。
• +name：表示这个人是当前组父亲的儿子，一组中可以有多行。
• ?name：询问这个人的最早祖先。
• 单独一个 $：输入结束。

所有父子关系先给出，随后给出询问。符号与名字之间可以有空格。

输出格式

每次询问输出一行，格式为“本人姓名 祖先姓名”，中间用一个空格隔开。

样例

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

Edward Arthur
Walter Arthur
Rodney George
Arthur Arthur

数据范围

每个姓名由 $6$ 个英文字母组成，首字母大写、其余字母小写。至多 $1000$ 组父子记录，总人数不超过 $50000$，家谱最多 $30$ 代，询问次数在 $1\sim50000$ 之间。