分块，但是5pts，求调qwq

//
// Created by shiro on 2023/8/3.
//
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 4e4 + 5;
const int maxk = 225;

int n, m, Q, tot, prex;
int a[maxn], tmp[maxn], blk[maxn];
int L[maxk], R[maxk], cnt[maxn];
int s[maxk][maxn];
bool vis[maxk];

struct node {
    int val, s;
} d[maxk][maxk];

void prework() {
    for(int i = 1; i <= n; i++) {
        blk[i] = (i-1)/Q + 1;
        if(blk[i] != blk[i-1]) R[blk[i-1]] = i-1, L[blk[i]] = i;
    }
    //处理块
    R[blk[n]] = n;
    for(int i = 1; i <= blk[n]; i++) {
        for(int j = 1; j <= tot; j++) s[i][j] = s[i-1][j];
        for(int j = L[i]; j <= R[i]; j++) s[i][a[j]]++;
    }
    //s[i][j]  表示1到i块间，j的出现次数
    for(int i = 1; i <= blk[n]; i++) {
        memset(cnt, 0, sizeof(cnt)); node p;
        p.val = p.s = 0;
        for(int j = i; j <= blk[n]; j++) {
            for(int k = L[j]; k <= R[j]; k++) {
                cnt[a[k]]++;
                if(cnt[a[k]] > p.s) {
                    p.val = a[k];
                    p.s = cnt[a[k]];
                }
                else if(cnt[a[k]] == p.s) p.val = min(p.val, a[k]);
            }
            d[i][j] = p;
        }
    }
    //d[i][j] 表示i块到j块之间的众数与出现次数
}

int main() {
    scanf("%d %d", &n, &m);
    Q = sqrt(n);

    for(int i = 1; i <= n; i++) scanf("%d", &a[i]), tmp[i] = a[i];
    sort(tmp+1, tmp+1+n);
    tot = unique(tmp+1, tmp+1+n) - tmp - 1;
    for(int i = 1; i <= n; i++) a[i] = lower_bound(tmp+1, tmp+1+tot, a[i]) - tmp;
    //输入&离散化
    prework();

    for(int i = 1; i <= m; i++) {
        int l, r; scanf("%d %d", &l, &r);
        l = ((l+prex-1)%n)+1, r = ((r+prex-1)%n)+1;
        if(l > r) swap(l, r);

        if(blk[r]-blk[l] < 2) {
            int ans = 0;
            for(int j = l; j <= r; j++) cnt[a[j]] = 0;
            for(int j = l; j <= r; j++) {
                cnt[a[j]]++;
                if(cnt[a[j]] > cnt[ans]) ans = a[j];
                else if(cnt[a[j]] == cnt[ans]) ans = min(ans, a[j]);
            }
            ans = tmp[ans];
            printf("%d\n", ans);
            prex = ans;
        }
        //散块
        else {
            int cl = blk[l]+1, cr = blk[r]-1;
            int ans = d[cl][cr].val;
            for(int j = l; j <= R[cl-1]; j++) cnt[a[j]] = 0, vis[a[j]] = false;
            for(int j = L[cr+1]; j <= r; j++) cnt[a[j]] = 0, vis[a[j]] = false;
            for(int j = l; j <= R[cl-1]; j++) cnt[a[j]]++;
            for(int j = L[cr+1]; j <= r; j++) cnt[a[j]]++;
            node p; p.s = p.val = 0;
            for(int j = l; j <= R[cl-1]; j++) {
                if(!vis[a[j]]) {
                    vis[a[j]] = true;
                    if(cnt[a[j]]+s[cr][a[j]]-s[cl-1][a[j]] > p.s) {
                        p.s = cnt[a[j]]+s[cr][a[j]]-s[cl-1][a[j]];
                        p.val = a[j];
                    }
                    else if(cnt[a[j]]+s[cr][a[j]]-s[cl-1][a[j]] == p.s) p.val = min(p.val, a[j]);
                }
            }
            for(int j = L[cr+1]; j <= r; j++) {
                if(!vis[a[j]]) {
                    vis[a[j]] = true;
                    if(cnt[a[j]]+s[cr][a[j]]-s[cl-1][a[j]] > p.s) {
                        p.s = cnt[a[j]]+s[cr][a[j]]-s[cl-1][a[j]];
                        p.val = a[j];
                    }
                    else if(cnt[a[j]]+s[cr][a[j]]-s[cl-1][a[j]] == p.s) p.val = min(p.val, a[j]);
                }
            }
            if(p.s > cnt[ans]+s[cr][ans]-s[cl-1][ans]) ans = p.val;
            else if(p.s == cnt[ans]+s[cr][ans]-s[cl-1][ans]) ans = min(ans, p.val);
            ans = tmp[ans];
            printf("%d\n", ans);
            prex = ans;
        }
        //整块加散块
    }
    return 0;
}