Let's do a dry run first to observe the behavior of the sequence. Let $$$a = [1, 2, 0, 2, 2]$$$. We observe that the sequence $$$s$$$ is $$$[1, 2, 0, 2, 2, 3, 1, 4, 0, 5, 2, 3, 1, 4, 0, 5, 2, ...]$$$. We observe that the sequence is periodic from $$$s_{n+1}$$$ onwards with a period of $$$n + 1$$$. We also observe that the periodic part from $$$s_{n+1}$$$ to $$$s_{2n + 1}$$$ is a permutation of integers $$$0, 1, 2, ..., n$$$ (in this case, $$$3, 1, 4, 0, 5, 2$$$). Here's a way to prove it.
We know that all elements in the sequence are bounded by $$$n$$$ because the first $$$n$$$ elements indeed satisfy according to the problem constraints, and the mex of any $$$n$$$ non-negative integers can be at most $$$n$$$. Obviously, all elements in the sequence are non-negative.
Finally, we have to prove that all elements in $$$s_{n+1}, s_{n+2}, ..., s_{2n+1}$$$ are distinct.
For the sake of contradiction, assume two indices $$$i$$$ and $$$j$$$ exist such that $$$n + 1 \leq i \lt j \leq 2n + 1$$$ and $$$s_i$$$ = $$$s_j$$$. Now, $$$s_j = \operatorname{mex}(s_{j-1}, s_{j-2}, ..., s_{j-n})$$$. Now, $$$s_i$$$ lies in $$$s_{j-1}, s_{j-2}, ..., s_{j-n}$$$ because $$$j \leq i + n$$$ however $$$s_i$$$ = $$$s_j$$$ and since $$$s_j$$$ is the mex of integers containing $$$s_i$$$, we get a contradiction. Hence, all integers in $$$s_{n+1}, s_{n+2}, ..., s_{2n + 1}$$$ are distinct and between $$$0$$$ and $$$n$$$ inclusive. Hence, all elements from $$$s_{n+1}$$$ and $$$s_{2n+1}$$$ form a permutation of $$$0, 1, 2, ..., n$$$. Now we have to prove that the sequence is periodic from term $$$n+1$$$ onwards with a period of $$$n+1$$$. This means for all $$$i \geq 2n + 2$$$, $$$s_i$$$ = $$$s_{i-(n+1)}$$$. We know that $$$s_{2n+2} = \operatorname{mex}(s_{2n+1}, s_{2n}, ..., s_{n+2})$$$. We know that all these $$$n$$$ integers are distinct and do not contain $$$s_{n+1}$$$. Hence, the mex is $$$s_{n+1}$$$ and $$$s_{2n+2}$$$ = $$$s_{n+1}$$$ Hence, all integers in $$$s_{n+2}, s_{n+3}, ..., s_{2n+2}$$$ are distinct because $$$s_{n+1}, s_{n+2}, ..., s_{2n+1}$$$ are distinct. Hence, by induction, it can be proven that any $$$n+1$$$ consecutive terms are distinct. This can also prove that any pair of elements from whose lower term starts from $$$n+1$$$ onwards that differ by $$$n+1$$$ are equal. Hence, the sequence is periodic from term $$$n+1$$$ onwards. Now, we have to calculate $$$s_{n+1}, s_{n+2}, ..., s_{2n+1}$$$. A brute force approach — calculating the mex of each element manually by taking the last $$$n$$$ elements takes $$$O(n)$$$ per computation for overall $$$O(n^2)$$$ time which is too slow. The problem now becomes similar to the sliding window mex problem where the array size is $$$2n + 1$$$ and the window size is $$$n$$$. We'll use a set called missing to keep track of the missing elements in the current sliding window. We'll erase the possibly missing element that comes inside the window. What about the one that leaves the window? We'll need to use a frequency array for this. Let $$$freq_i$$$ be the frequency of element $$$i$$$ in the current window for $$$0 \leq i \leq n$$$. Now, we'll increment the frequency of the element coming inside the window and decrement the frequency of the element leaving the window. If the frequency of the element leaving the window becomes $$$0$$$, that element is no longer present in the window, and we can insert it back into the missing elements set. Each time, we have the current element = smallest missing element in the set, that is *missing.begin(); because sets are always sorted. Hence, we can calculate $$$s_{n+1}, s_{n+2}, ..., s_{2n+1}$$$ in $$$O(\log n)$$$ time, for an overall time complexity of $$$O(n \log n)$$$ Denote $$$perm_i$$$ = $$$s_{n+i}$$$ for all $$$1 \leq i \leq n + 1$$$. Now, what is the value of $$$s_k$$$ for some value of $$$k$$$? If $$$k \leq n$$$, the answer is simply $$$a_k$$$. Else, we know that the index of the answer in the periodic part is $$$(k \mod {n + 1}) + 1$$$. For example, if $$$k = n + 2$$$, the index will be $$$2$$$. This repeats every $$$n + 1$$$ terms. Hence, the answer is $$$perm_{(k\mod{n + 1}) + 1}$$$. Each query takes $$$O(1)$$$ time. Hence, the overall time complexity of the code will be $$$O(n \log n + q$$$).

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    vector<int> freq(n + 1, 0);
    set<int> missing;
    for(int i = 1; i <= n; i++) freq[a[i]]++;
    for(int i = 0; i <= n; i++) {
        if(freq[i] == 0) missing.insert(i);
    }
    vector<int> perm(n + 2);
    for(int i = 1; i <= n + 1; i++) {
        perm[i] = *missing.begin();
        missing.erase(perm[i]);
        freq[perm[i]]++;
        if(i <= n) {
            freq[a[i]]--;
            if(freq[a[i]] == 0) missing.insert(a[i]);
        }
    }
    for(int i = 0; i < q; i++) {
        long long k;
        cin >> k;
        if(k <= n) cout << a[k];
        else {
            int idx = (k % (n + 1)) + 1;
            cout << perm[idx];
        }
        if(i == q - 1) cout << endl;
        else cout << ' ';
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}