时间限制：1000ms　内存限制：512MB

结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

某输入法应用在设备本地维护一个词库，词库中的每个条目是一个单词。用户在检索框中输入一段字符串作为前缀，系统就从词库中选出候选词返回给用户。本题中，词库共收录 $n$ 个互不相同的单词，每个单词由小写英文字母构成。

一次检索由两部分组成：一个字符串 $p$ 和一个正整数 $k$。系统先找出词库中所有以 $p$ 为前缀的单词，把它们按字典序从小到大排成一列，然后返回这一列中字典序第 $k$ 小的那个单词。若以 $p$ 为前缀的单词总数不足 $k$ 个（包括一个都没有），系统无法选出第 $k$ 个单词，此时返回 $-1$。

一个单词 $w$ 以字符串 $p$ 为前缀，指 $w$ 的长度不小于 $p$ 的长度，且 $w$ 的前 $|p|$ 位依次与 $p$ 的每一位相同，即 $w$ 的开头正好是 $p$。两个单词的字典序大小按如下规则比较：从第一个字符起逐位比较，若在第 $i$ 位字符不同，则字符更小（按字母表顺序）的单词更小；若比较到其中一个单词结束仍全部相同，则较短的那个单词更小。

输入格式

从文件 dict.in 中读入数据。

• 第一行一个正整数 $n$，表示词库中单词的个数。
• 接下来 $n$ 行，每行一个字符串，表示一个单词。单词由小写英文字母构成，互不相同。
• 接下来一行一个正整数 $q$，表示检索次数。
• 接下来 $q$ 行，每行一个字符串 $p$ 和一个正整数 $k$，表示一次检索的前缀与所要求的序号。

输出格式

输出到文件 dict.out 中。

共 $q$ 行，每行一个字符串，依次对应每次检索的答案；若对应检索没有结果，输出 -1。

样例

样例 1 输入

6
apple
app
banana
band
book
a
4
app 1
b 3
app 3
z 1

样例 1 输出

app
book
-1
-1

样例 1 解释

以 b 为前缀的单词有 banana、band、book 三个，按字典序排列为 banana、band、book，第 3 个是 book。以 app 为前缀的单词只有 app、apple 两个，不足 3 个；没有任何单词以 z 为前缀，这两次检索均返回 -1。

样例 2 输入

5
cat
catalog
catfish
dog
door
3
cat 2
cata 1
d 2

样例 2 输出

catalog
catalog
door

样例 2 解释

以 cat 为前缀的单词有 cat、catalog、catfish 三个。cat 是另外两个单词的前缀，按字典序最小，排在第一位；catalog 与 catfish 比较时，第 4 个字符 a 小于 f，故 catalog 在前。排列为 cat、catalog、catfish，第 2 个是 catalog。以 d 为前缀的单词有 dog、door，排列为 dog、door，第 2 个是 door。

样例 3 输入

5
sun
sunny
sunshine
moon
moonlight
2
sun 3
sun 4

样例 3 输出

sunshine
-1

样例 3 解释

以 sun 为前缀的单词有 sun、sunny、sunshine 三个。sun 是另外两个单词的前缀，排在第一位；sunny 与 sunshine 比较时，第 4 个字符 n 小于 s，故 sunny 在前。排列为 sun、sunny、sunshine，第 3 个是 sunshine。该前缀下的单词总数恰为 3，而第二次检索要求第 4 个，超出候选总数，返回 -1。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 10^5$，每个单词长度 $\ge 1$，所有单词的总长度 $\le 10^6$；
• 每个单词以及每次检索的前缀 $p$ 均由小写英文字母构成，单词互不相同；
• $1 \le q \le 10^5$，所有前缀的总长度 $\le 10^6$；
• $1 \le k \le n$。

各测试点的约束如下：

特殊性质 A：所有检索的 $k$ 均为 $1$。