← 返回题目列表

Codeforces · 670/C

C. 电影院

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

莫斯科正在主办一场大型国际会议,有来自不同国家的 n 位科学家参加。每位科学家都精通一种语言。为了方便起见,我们用 1 到 109 的整数枚举世界上所有的语言。

会议结束后的晚上,n位科学家决定去看电影。他们来到的电影院里有m部电影。每部电影都有两个不同的数字:音频语言索引和字幕语言索引。来看电影的科学家,如果他知道电影的音频语言,他会非常高兴;如果他知道字幕语言,他会几乎满意;如果他不知道其中一种或另一种语言,他会不满意(注意,每部电影的音频语言和字幕语言总是不同的)。

科学家们决定一起去看同一部电影。你必须帮助他们选择电影,以使非常高兴的科学家的数量尽可能多。如果有几部这样的电影,请从其中选择一部能够最大限度地增加几乎满意的科学家的数量。

输入

输入的第一行包含一个正整数 n (1 ≤ n ≤ 200 000) — 科学家的数量。

第二行包含n个正整数a1, a2, ..., an (1 ≤ ai ≤ 109),其中ai是第i位科学家所知道的语言的索引。

第三行包含一个正整数 m (1 ≤ m ≤ 200 000) — 电影院的电影数量。

第四行包含m个正整数b1,b2,...,bm(1≤bj≤109),其中bj是第j部电影的音频语言的索引。

第五行包含m个正整数c1,c2,...,cm(1≤cj≤109),其中cj是第j部电影的字幕语言索引。

保证每部电影的音频语言和字幕语言都不同,即bj≠cj。

输出

打印单个整数——科学家应该去看的电影的索引。看完这部电影后,非常高兴的科学家数量应该尽可能多。如果电影院里有几部这样的电影,你需要从其中选择一部,看完后就会有尽可能多的几乎满意的科学家。

如果有多个可能的答案,请打印其中任何一个。

示例

输入 #1

3
2 3 2
2
3 2
2 3

输出 #1

2

输入 #2

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

输出 #2

1

注意

在第一个样本中,科学家必须去看索引为 2 的电影,因为在这种情况下,第 1 和第 3 科学家将非常高兴,第 2 科学家将几乎满意。

在第二个测试用例中,科学家可以观看索引为 1 或索引 3 的电影。在观看这些电影中的任何一部之后,恰好有两个科学家会非常满意,而其他所有科学家都会不满意。