题目描述

一项足球赛事采用单败淘汰制，一支队伍输掉一场比赛后立即被淘汰。参赛队伍数 $n$ 是 2 的幂，每支队伍在赛事开始前会被分配一个互不相同的种子编号 $0,1,\ldots,n-1$。

比赛对阵按以下递归规则确定：

1. 设当前剩余队伍数为 $N$；
2. 若 $N=1$，赛事结束；
3. 否则，将当前队伍两两配对，使每场比赛中两支队伍的原始种子编号之和为 $N-1$；
4. 每场比赛都由种子编号较小的队伍获胜；
5. 对所有胜者递归执行相同过程。

例如，在 8 支队伍的赛事中，第一轮对阵为 $0$ 对 $7$、$1$ 对 $6$、$2$ 对 $5$、$3$ 对 $4$；第二轮对阵为 $0$ 对 $3$、$1$ 对 $2$；最后由 $0$ 对 $1$。

不同分支的比赛可以交错进行：只要一场比赛的双方都已经晋级到相应轮次，这场比赛就可以开始。因此，某场第二轮比赛可能早于另一个分支的第一轮比赛结束。

现在给出所有参赛队伍，以及截至目前已经进行的全部比赛。每场比赛给出胜者和败者；输入中的比赛顺序任意，不代表实际进行顺序。你需要为所有队伍分配种子，使给出的比赛记录能够由上述赛事产生。若存在多种合法分配，选择按种子编号排列的队名序列中字典序最小的一种。

设完整种子序列为 $A$，其中 $A_i$ 是种子 $i$ 对应的队伍。若两个分配 $A,B$ 第一次不同的位置为 $i$，且 $A_i<B_i$，则称 $A$ 的字典序更小。队名按通常的字符串字典序比较：字符 '0' 至 '9' 排在 'A' 至 'Z' 之前，若一个字符串是另一个的前缀，则较短者更小。

若比赛记录不可能来自一场合法赛事，输出 -1；否则回答所有给定种子编号对应的队伍名称。查询中允许重复出现同一种子编号。

输入格式

第一行一个整数 $n$，表示参赛队伍数。

第二行包含 $n$ 个互不相同的队伍名称，以空格分隔。

第三行一个整数 $m$，表示已经进行的比赛数量。

接下来 $m$ 行，每行两个队伍名称 winner loser，分别表示该场比赛的胜者和败者。

下一行一个整数 $q$，表示查询数量。

最后一行包含 $q$ 个整数 $s_1,s_2,\ldots,s_q$，表示需要查询的种子编号。

输出格式

若比赛记录不合法，输出一行 -1。

否则输出一行 $q$ 个队伍名称，第 $i$ 个名称是字典序最小合法分配中种子 $s_i$ 对应的队伍，名称之间以一个空格分隔。

样例 1

4
CELTICS LAKERS SPURS PISTONS
3
CELTICS LAKERS
CELTICS PISTONS
LAKERS SPURS
4
0 1 2 3

CELTICS LAKERS SPURS PISTONS

样例 2

4
GIANTS PATRIOTS CHARGERS PACKERS
1
PATRIOTS CHARGERS
4
3 2 1 0

PACKERS CHARGERS PATRIOTS GIANTS

只有一场比赛已经进行。虽然存在多种合法排位，但字典序最小的完整种子序列为 GIANTS PATRIOTS CHARGERS PACKERS。

样例 3

8
REDSOX PHILLIES METS DODGERS ORIOLES BLUEJAYS CUBS ANGELS
3
METS ANGELS
METS CUBS
ORIOLES ANGELS
8
0 1 2 3 4 5 5 5

-1

ANGELS 不可能在单败淘汰赛中输掉两场比赛。

样例 4

8
REDSOX PHILLIES METS DODGERS ORIOLES BLUEJAYS CUBS ANGELS
4
METS ANGELS
METS CUBS
CUBS DODGERS
REDSOX PHILLIES
8
0 1 2 3 4 5 6 7

BLUEJAYS METS CUBS REDSOX PHILLIES DODGERS ANGELS ORIOLES

METS 与 CUBS 的第二轮比赛可以在另一个分支的首轮比赛结束前进行。

样例 5

16
A B C D E F 8 H I 3 9 L 4 N O P
5
P A
B H
D C
D E
E N
8
0 2 0 0 3 4 7 2

3 8 3 3 D E P 8

查询中可以多次出现同一个种子编号。

数据范围与保证

• $n$ 是 2 的非负整数次幂，且 $1\le n\le1024$；
• 每个队伍名称由 1 至 20 个大写英文字母或数字组成；
• 所有队伍名称互不相同；
• $0\le m\le625$；
• 每场比赛中的两个名称均属于参赛队伍，且一支队伍不会与自己比赛；
• 输入不会重复列出同一场比赛；
• $1\le q\le50$；
• $0\le s_i<n$。

比赛记录本身不保证能够组成合法赛事。

来源

改编自 TopCoder TournamentSeeding（PM9802，SRM 408 Div.1 Hard），已转换为标准输入输出形式。