← 返回题目列表

Codeforces · 1181/D

D. 灌溉

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

Misha 从小就对送水感兴趣。这就是为什么他的母亲送他参加一年一度的创新灌溉奥林匹克竞赛 (IOI)。来自伯兰各地的学生在那里比赛,展示他们的浇水技巧。举办这样一届奥运会的费用极其昂贵,因此在第一届$$$n$$$奥运会之后,组织者引入了以下主办城市选择规则。

奥运会主办城市的选择方式如下。伯兰有 $$$m$$$ 个城市希望举办奥运会,编号从 $$$1$$$ 到 $$$m$$$。下一届奥运会的主办城市被确定为此前举办奥运会次数最少的城市。如果有多个这样的城市,则选择其中指数最小的城市。

Misha 的母亲对奥运会在某些特定年份的举办地感兴趣。她唯一知道的信息就是上面的选拔规则和第一届$$$n$$$奥运会的主办城市。帮助她,如果你成功了,她会要求米莎避免淹没你的房子。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1 \leq n, m, q \leq 500\,000$$$) — 规则引入之前举办的奥运会数量、伯兰希望举办奥运会的城市数量以及 Misha 的母亲感兴趣的年数分别在。

下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq m$$$),其中 $$$a_i$$$ 表示第 $$$i$$$ 年举办奥运会的城市。请注意,在引入规则之前,主办城市是任意选择的。

接下来的每一行 $$$q$$$ 都包含一个整数 $$$k_i$$$ ($$$n + 1 \leq k_i \leq 10^{18}$$$) - Misha 的母亲对主办城市感兴趣的年份。

输出

打印 $$$q$$$ 整数。其中第 $$$i$$$ 应该是 $$$k_i$$$ 年举办奥运会的城市。

示例

输入 #1

6 4 10
3 1 1 1 2 2
7
8
9
10
11
12
13
14
15
16

输出 #1

4
3
4
2
3
4
1
2
3
4

输入 #2

4 5 4
4 4 5 1
15
9
13
6

输出 #2

5
3
3
3

注意

在第一个示例中,Misha 的母亲对规则引入后的前 $$$10$$$ 年感兴趣。历届主办城市分别为4、3、4、2、3、4、1、2、3、4。

在第二个示例中,引入新城市后的主办城市为 2, 3, 1, 2, 3, 5, 1, 2, 3, 4, 5, 1。