各操作を出現回数が同じ要素をまとめて追加することを考えると、操作は以下のようにまとめることができます。

• \(A\) における出現回数順に \((1,2,\ldots,M)\) を安定ソートした列を \((P_1,P_2,\ldots,P_M)\) とする。また、\(A\) における \(P_i\) の出現回数を \(V_i\) とする。
• \(k=1,2,\ldots,M\) に対して以下を行う。
  • \(A\) の末尾に \((P_1,P_2,\ldots,P_k)\) をソートした列を追加する操作を \(V_{k+1}-V_k\) 回行う。ただし、 \(V_{M+1}=\infty\) とする。

\(k=k_0\) の場合の操作が終わった際の \(A\) の長さは \(\displaystyle N+\sum_{i=1}^{k_0}k(V_{k+1}-V_k)\) と表せるので、\(A_X\) は \(k\) がいくつの時に追加された要素か・\((P_1,P_2,\ldots,P_k)\) をソートした列の何番目の要素かを二分探索で求めることができます。

また、\((k,v)\) のペアが与えられ、\((P_1,P_2,\ldots,P_k)\) の中で小さい方から \(v\) 番目の要素を求めるクエリはオフラインで Fenwick Tree を用いることで高速に計算することができます。

以上を適切に実装することでこの問題に正答することができます。

実装例(Python3)

import sys
input = sys.stdin.readline


class BIT:
    def __init__(self, n: int):
        self.a = [0] * (n + 1)

    def add(self, i: int, x: int) -> None:
        i += 1
        while i < len(self.a):
            self.a[i] += x
            i += i & -i

    def sum(self, *args) -> int:
        if len(args) == 1:
            r = args[0]
            s = 0
            while r:
                s += self.a[r]
                r -= r & -r
            return s
        else:
            l, r = args
            return self.sum(r) - self.sum(l)

    # minimize i s.t. sum(i) >= w
    def lower_bound(self, w: int) -> int:
        x = 0
        n = len(self.a) - 1
        k = 1 << (n.bit_length() - 1)
        while k:
            if x + k <= n and self.a[x + k] < w:
                w -= self.a[x + k]
                x += k
            k >>= 1
        return x + 1


n, m = map(int, input().split())
a = [int(x) - 1 for x in input().split()]
c = [0] * m
for v in a:
    c[v] += 1
s = [(c[i], i) for i in range(m)]
s.sort()
r = [0] * (m + 1)
r[0] = n
for i in range(m - 1):
    r[i + 1] = (i + 1) * (s[i + 1][0] - s[i][0]) + r[i]
r[m] = 10**18 + 2026
q = int(input())
ans = [-1] * q
que = []
for i in range(q):
    x = int(input())
    if x <= n:
        ans[i] = a[x - 1]
        continue
    ng, ok = 0, m
    while ok - ng != 1:
        vs = (ok + ng) >> 1
        if r[vs] >= x:
            ok = vs
        else:
            ng = vs
    x -= r[ng] + 1
    x %= ok
    que.append((ok, x, i))
que.sort()
fw = BIT(m)
idx = 0
for ok, x, i in que:
    while idx < ok:
        fw.add(s[idx][1], 1)
        idx += 1
    ans[i] = fw.lower_bound(x + 1) - 1
for v in ans:
    print(v + 1)