家谱协会的数据库中有若干行数据：

若一行数据以#开头，则#后面的人名为父亲或母亲的姓名；

若一行数据以+开头，则+后面的人名为上一个以#开头的行的父亲或母亲的儿子或女儿的姓名；

接下来，有若干行数据以?开头，?后面的人名为需要查询其祖先的人的姓名。

祖先：指在家谱协会的数据库中不存在父亲或母亲的人。

不超过10^5行，格式如题目表述。每个人名首字母为大写英文字母，后续为小写英文字母，且总长度不超过32个字符。

数据保证：不存在重名的人；

数据保证：以#开头的行的人名是按出生顺序排列的；

数据保证：以#开头的行的人名没有相同的；

数据保证：第一行以#开头；

数据保证：以#开头的行后面至少有一个以+开头的行；

数据保证：以?开头的行的人名一定存在于之前提供的以#或+开头行的人名中。

对于每行查询，输出一行，格式为：单个空格分割的两个字符串，第一个为要查询的人的姓名，第二个为其祖先姓名。