AT_abc449_e.[ABC449E] A += v

给定整数 $N, M$ 和一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$，序列中每个元素都在 $1$ 到 $M$ 之间（包含 $1$ 和 $M$）。

对这个整数序列 $A$ 重复执行如下操作 $10^{100}$ 次：

• 记 $v$ 为 $1$ 到 $M$ 中，在 $A$ 中出现次数最少的整数。如果存在多个这样的 $v$，取最小的那个。然后将 $v$ 加到 $A$ 的末尾。

有 $Q$ 个询问。第 $i$ 个询问给定整数 $X_i$，请你在执行操作 $10^{100}$ 次之后，输出 $A_{X_i}$ 的值。

输入从标准输入给出，格式如下：

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

输出 $Q$ 行。

第 $i$ 行输出第 $i$ 个询问的答案。

样例解释 1

初始时，$A=(1,1,2)$。每次操作后，$A$ 的变化如下：

• 第一次操作：$A$ 中 $1,2,3$ 的出现次数分别为 $2,1,0$，所以 $v=3$，将 $v$ 加入 $A$ 末尾，$A=(1,1,2,3)$。
• 第二次操作：$A$ 中 $1,2,3$ 的出现次数分别为 $2,1,1$，所以 $v=2$，将 $v$ 加入 $A$ 末尾，$A=(1,1,2,3,2)$。
• 第三次操作：$A$ 中 $1,2,3$ 的出现次数分别为 $2,2,1$，所以 $v=3$，将 $v$ 加入 $A$ 末尾，$A=(1,1,2,3,2,3)$。
• $\vdots$

重复很多次后，$A$ 变为 $A=(1,1,2,3,2,3,1,2,\ldots)$。

约束条件

• $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}$
• 所有输入值均为整数。

由 ChatGPT 5 翻译