← 返回题目列表

Codeforces · 59/D

D. 团队安排

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

最近,伯兰州立大学奥林匹克程序员培训中心的个人培训课程已经结束。根据这些训练的结果,球队将组成即将到来的球队赛季。每个团队由三人组成。中心所有学生拥有1到3n的号码,所有队伍拥有1到n的号码。将学生分成小组的方式如下:当有人不属于小组时,从其中选出总成绩最好的人(新小组的队长),该人根据自己的优先顺序从剩下的人中选择两名队友。每个人的优先事项列表表示为除了他自己之外在该中心的其余 3n - 1 名学生的排列。

您将获得个人训练课程的结果,该结果是从 1 到 3n 的数字排列,其中第 i 个数字是赢得第 i 名的学生的人数。没有两个学生共用一个位置。您还可以按照已组建的团队的创建顺序进行排列。您的任务是确定学生编号 k 的优先级列表。如果有多个优先级列表,请选择字典顺序最小的一个。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105),它是最终球队的数量。第二行包含从 1 到 3n 的 3n 个空格分隔的整数,它们是个人训练课程的结果。保证每个学生在结果中只出现一次。

然后接下来的 n 行每行包含从 1 到 3n 的三个整数 — 每行描述给定团队的成员。一个团队的成员可以按任意顺序列出,但团队本身按创建顺序列出。保证了安排是正确的,即每个学生都是一个团队的成员,并且这些团队确实可以使用上述方法根据给定的结果创建。

最后一行包含数字 k (1 ≤ k ≤ 3n),它是应找到优先级列表的学生的编号。

输出

打印 3n - 1 个数字 — 按字典顺序排列的学生编号 k 的最小优先级列表。

字典顺序比较由现代编程语言中的标准 < 运算符执行。如果存在这样的 i (1 ≤ i ≤ 3n),即 ai < bi,并且对于任何 j (1 ≤ j < i) aj = bj,则列表 a 按字典顺序小于列表 b。请注意,列表 1 9 10 按字典顺序小于列表 1 10 9。也就是说,列表的比较与行的比较不同。

示例

输入 #1

3
5 4 1 2 6 3 7 8 9
5 6 2
9 3 4
1 7 8
4

输出 #1

2 3 5 6 9 1 7 8

输入 #2

3
5 4 1 2 6 3 7 8 9
5 6 2
9 3 4
1 7 8
8

输出 #2

1 2 3 4 5 6 7 9

输入 #3

2
4 1 3 2 5 6
4 6 5
1 2 3
4

输出 #3

5 6 1 2 3