生成机制

题目描述

Y 同学正在研究一个有趣的序列生成机制。

给定两个正整数 $N, M$ 和一个长度为 $N$ 的初始整数序列 $A = (A_1, A_2, \dots, A_N)$，其中每个元素都满足 $1 \le A_i \le M$。

接下来，Y 同学将对序列 $A$ 执行 $10^{100}$ 次以下操作：

• 在 $1$ 到 $M$ 这 $M$ 个整数中，找到在当前序列 $A$ 中出现次数最少的整数 $v$。如果存在多个出现次数最少的整数，则选择其中数值最小的那个。
• 将选出的整数 $v$ 追加到序列 $A$ 的末尾。

由于操作次数非常多，序列 $A$ 的长度将变得极其巨大。

现在，Y 同学提出了 $Q$ 个询问。第 $i$ 个询问给出一个正整数 $X_i$，请你帮助他计算，在执行完所有 $10^{100}$ 次操作后，序列 $A$ 中第 $X_i$ 个元素（下标从 $1$ 开始计数）的值是多少。

输入格式

第一行包含两个由空格分隔的正整数 $N$ 和 $M$。

第二行包含 $N$ 个由空格分隔的正整数 $A_1, A_2, \dots, A_N$，表示初始序列 $A$。

第三行包含一个正整数 $Q$，表示询问的次数。

接下来 $Q$ 行，每行包含一个正整数 $X_i$，表示第 $i$ 个询问查询的序列下标。

输出格式

输出共 $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

样例输入 #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

数据范围与约定

对于 $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}$