分数: 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