← 返回题目列表

AtCoder · abc449_e

H. A 加上 v

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

分数: 475 点

问题陈述

给你整数 N, M 和一个整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N 其中每个元素位于 1 和 M,包括在内。

执行以下操作 此整数序列上的 10^{100} 次 A:

  • 让 v 是之间的整数 1 和 M,包含在内,出现次数最少 A。如果有多个这样的 v,取其中最小的。然后,追加 v 到年底 A.

你被给予 Q 查询。的 i-th 查询给出一个整数 X_i,所以找到值 A_{X_i} 执行操作后 10^{100} 次。

约束

  • 1\le N,M\le 5\times 10^5
  • 1\le A_i \le M
  • 1\le Q\le 2\times 10^5
  • 1\le X_i \le 10^{18}
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
A_1 A_2 \ldots A_N
Q
X_1
X_2
\vdots
X_Q

输出

输出 Q 行。

的 i- 第行应包含以下问题的答案 i第一个查询。


示例输入 1

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

示例输出 1

1
1
2
3
2
3
1
2

最初, A=(1,1,2)。每一次操作, A 更改如下:

  • 第一次操作:计数 1, 2, 3 in A 是 2, 1, 0 分别,所以 v=3。追加 v 到年底 A,给予 A=(1,1,2,3).
  • 第二次操作:计数 1, 2, 3 in A 是 2, 1, 1 分别,所以 v=2。追加 v 到年底 A,给予 A=(1,1,2,3,2).
  • 第三次操作:计数 1, 2, 3 in A 是 2, 2, 1 分别,所以 v=3。追加 v 到年底 A,给予 A=(1,1,2,3,2,3).
  • \vdots

执行操作后 10^{100} 次, A 变为 A=(1,1,2,3,2,3,1,2,\ldots).


示例输入 2

7 30
20 26 3 14 4 4 9
10
31
9
21
23
97
99
30
79
57
3

示例输出 2

30
2
18
21
7
9
29
19
27
3