#CF670C. 看电影

看电影

CodeForces-670C

题目描述

\hspace{15pt}莫斯科举办了一场国际会议,来自不同国家的 nn 位科学家参加了这次盛会。每位科学家只会一种语言。为了方便,我们用 11 到 10910^9 的整数为全世界的语言编号。

\hspace{15pt}会议结束的晚上,这 nn 位科学家决定一起去看电影。电影院里有 mm 部电影,每部电影都有两个不同的数字标识:音频语言编号和字幕语言编号。

\hspace{15pt}对于一部电影,若某位科学家懂得它的音频语言,这位科学家会感到超级开心;若他不懂得音频语言、但懂得字幕语言,他会觉得还算满意;若两种语言都不懂,他则不开心。

\hspace{15pt}科学家们决定一起看同一部电影。请你帮他们选出一部电影,使得超级开心的科学家人数尽可能多;如果有好几部电影都能达到这个最大值,则从中选一部让还算满意的科学家人数也最多的电影。

输入格式

\hspace{15pt}第一行输入一个整数 n(1≦n≦2×105)n \left(1 \leqq n \leqq 2 \times 10^5\right) 代表科学家人数。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(1 \leqq a_i \leqq 10^9\right)$,其中 aia_i 代表第 ii 位科学家懂得的语言编号。

\hspace{15pt}第三行输入一个整数 m(1≦m≦2×105)m \left(1 \leqq m \leqq 2 \times 10^5\right) 代表电影数量。

\hspace{15pt}第四行输入 mm 个整数 $b_1, b_2, \dots, b_m \left(1 \leqq b_j \leqq 10^9\right)$,其中 bjb_j 代表第 jj 部电影的音频语言编号。

\hspace{15pt}第五行输入 mm 个整数 $c_1, c_2, \dots, c_m \left(1 \leqq c_j \leqq 10^9\right)$,其中 cjc_j 代表第 jj 部电影的字幕语言编号。

\hspace{15pt}保证对每部电影都有 bj≠cjb_j \neq c_j。

输出格式

\hspace{15pt}在一行上输出一个整数,代表科学家们应该观看的电影编号。

\hspace{15pt}如果存在多部满足要求的电影,输出其中任意一部即可,系统会自动判定答案是否正确。注意,自测运行功能可能因此返回错误结果,请自行检查答案正确性。

测试样例

3
2 3 2
2
3 2
2 3
2

样例 1 解释

\hspace{15pt}科学家们懂得的语言编号依次为 2,3,22, 3, 2,即懂语言 22 的有 22 人,懂语言 33 的有 11 人。

∙ \hspace{23pt}\bullet\,第 11 部电影的音频语言为 33、字幕语言为 22,超级开心的有 11 人,还算满意的有 22 人;

∙ \hspace{23pt}\bullet\,第 22 部电影的音频语言为 22、字幕语言为 33,超级开心的有 22 人,还算满意的有 11 人。

\hspace{15pt}第 22 部电影的超级开心人数更多,因此答案是 22。

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

样例 2 解释

\hspace{15pt}科学家们懂得的语言中,语言 11 和语言 33 各有 22 人懂得,语言 66 和语言 77 各有 11 人懂得。

∙ \hspace{23pt}\bullet\,第 11 部电影:音频语言 11,字幕语言 22,超级开心 22 人,还算满意 00 人;

∙ \hspace{23pt}\bullet\,第 22 部电影:音频语言 22,字幕语言 33,超级开心 00 人,还算满意 22 人;

∙ \hspace{23pt}\bullet\,第 33 部电影:音频语言 33,字幕语言 44,超级开心 22 人,还算满意 00 人;

∙ \hspace{23pt}\bullet\,第 44 部电影:音频语言 44,字幕语言 55,超级开心 00 人,还算满意 00 人;

∙ \hspace{23pt}\bullet\,第 55 部电影:音频语言 55,字幕语言 11,超级开心 00 人,还算满意 22 人。

\hspace{15pt}超级开心人数最多为 22 人,此时第 11 部和第 33 部电影的还算满意人数都是 00,两部电影都满足要求,输出其中任意一部即可,样例输出为 11。