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。