#include <bits/stdc++.h>
#define il inline
#define re register
#define ri re int
#define fr(a, b, c) for (ri a = (b); a <= (c); ++a)
#define ur(a, b, c) for (ri a = (b); a >= (c); --a)
using namespace std;

const int N = 60005, SN = 505;

int n, m, a[N], len, tot, l[SN], r[SN], pos[N], b[SN][SN], c[SN][N], tmp[N], cnt[N], ans, x, y, lastans;
unordered_map<int, int> mp;

il void read(int &a, ri ch = 0) {
    while (!isdigit(ch = getchar()))
        ;
    for (a = 0; isdigit(ch); ch = getchar())
        a = (a << 3) + (a << 1) + (ch ^ 48);
}
void write(ri x) {
    if (x > 9)
        write(x / 10);
    putchar(x % 10 ^ 48);
}
il void prework() {
    memcpy(tmp, a, sizeof(a));
    sort(tmp + 1, tmp + n + 1);
    ri L = unique(tmp + 1, tmp + n + 1) - tmp - 1;
    fr(i, 1, L) mp[tmp[i]] = i;
    fr(i, 1, n) a[i] = mp[a[i]];
    len = sqrt(n), tot = (n - 1) / len + 1;
    fr (i, 1, tot) {
        l[i] = r[i - 1] + 1;
        r[i] = r[i] + len;
        if (i == tot)
            r[i] = n;
        fr(j, l[i], r[i]) pos[j] = i;
    }
    fr (i, 1, tot) {
        memset(cnt, 0, sizeof(cnt)), ans = 0;
        fr (j, i, tot) {
            fr (k, l[j], r[j]) {
                cnt[a[k]]++;
                if (cnt[a[k]] > cnt[ans] || cnt[a[k]] == cnt[ans] && a[k] < ans)
                    ans = a[k];
            }
            b[i][j] = ans;
        }
        fr(j, 1, n) c[i][j] = c[i - 1][j];
        fr(j, l[i], r[i]) c[i][a[j]]++;
    }
    memset(cnt, 0, sizeof(cnt)), ans = 0;
}
#define get(k) (cnt[k] + c[q - 1][k] - c[p][k])
int query(int x, int y) {
    if (pos[x] == pos[y]) {
        ans = 0;
        fr(i, x, y) cnt[a[i]]++;
        fr (i, x, y) {
            if (cnt[a[i]] > cnt[ans] || cnt[a[i]] == cnt[ans] && a[i] < ans)
                ans = a[i];
        }
        fr(i, x, y) cnt[a[i]]--;
        return ans;
    }
    int p = pos[x], q = pos[y];
    ans = b[p + 1][q - 1];
    fr(i, x, r[p]) cnt[a[i]]++;
    fr(i, l[q], y) cnt[a[i]]++;
    fr(i, x, r[p]) {
        if (get(a[i]) > get(ans) || get(a[i]) == get(ans) && a[i] < ans)
            ans = a[i];
    }
    fr(i, l[q], y) {
        if (get(a[i]) > get(ans) || get(a[i]) == get(ans) && a[i] < ans)
            ans = a[i];
    }
    fr(i, x, r[p]) cnt[a[i]]--;
    fr(i, l[q], y) cnt[a[i]]--;
    return ans;
}
int main() {
    read(n), read(m);
    fr(i, 1, n) read(a[i]);
    prework();
    while (m--) {
        read(x), read(y);
        x = (x + lastans - 1) % n + 1, y = (y + lastans - 1) % n + 1;
        if (x > y)
            swap(x, y);
        write(lastans = tmp[query(x, y)]), putchar('\n');
    }
    return 0;
}