← 返回题目列表

Codeforces · 100/G

G. 为专辑命名

中文机器翻译题面 查看原题

著名歌手Aryo即将推出他的伟大作品的新专辑!

不幸的是,这些天有很多专辑,Aryo想为他的专辑选择一个新的名称,一个没有使用过或者至少最近没有使用过的名称。

他有一份所有使用过的专辑名称以及专辑出版年份的列表。他还列出了适合他专辑的名字。

如果他找到一个以前没有使用过的合适的名字,他就会使用它。否则他会尽可能使用很久以前用过的名字。如果找到两个这样的名称(未使用过或在同一年使用过),他将使用按字母顺序排列最新的名称。

帮他命名他的专辑。

输入

第一行包含一个整数 n (0 ≤ n ≤ 105),即已使用名称的数量。

接下来的 n 行每行包含一个字符串(专辑名称)和一个整数(专辑出版年份)。专辑名称由小写拉丁字母组成,最多包含 14 个字母。年份范围为 [1900, 2011]。

下面一行包含一个整数 m (1 ≤ m ≤ 104),即合适的专辑名称的数量。

接下来的 m 行每行包含一个字符串——一个合适的名称。它最多包含 14 个小写拉丁字母。

所有专辑名称和合适名称均非空。

输出

写入单个字符串。新专辑的名称。

示例

输入 #1

3
eyesonme 2008
anewdayhascome 2002
oneheart 2003
2
oneheart
bienbien

输出 #1

bienbien

输入 #2

2
nasimevasl 2003
basetareha 2006
2
nasimevasl
basetareha

输出 #2

nasimevasl