%%%%%%%%%%%%%%%%% TNT %%%%%%%%%%%%%%%

# include <iostream>
# include <cstdio>
# include <algorithm>
# include <cmath>
# define MAXN 40005

using namespace std;

int rd(){
    int x = 0; char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >='0' && ch <='9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }    
    return x;
}

// Partition Section

int a[MAXN], blk[MAXN], sizB;
int tmpLWB[MAXN]; // 离散化的辅助数组
int sum[250][MAXN]; // 处理每块中的颜色前缀和
int mod[250][250]; // mod[i][j] 从 i 块到 j 块的最小下标的众数
int cntCol[MAXN]; // 用于询问记录的桶

void Init(int n){

    // 离散化
    sort(tmpLWB+1, tmpLWB+n+1);
    int tmpL = unique(tmpLWB+1, tmpLWB+n+1) - tmpLWB - 1;

    for(int i = 1; i <= n; i++){
        a[i] = lower_bound(tmpLWB+1, tmpLWB+1+tmpL, a[i]) - tmpLWB;
    }

    // 前缀和处理
    int cntB = (n - 1) / sizB + 1; // 块的个数

    for(int i = 1; i <= n; i++){
        sum[blk[i]][a[i]] += 1;
    }
    for(int i = 1; i <= cntB; i++){
        for(int j = 1; j <= tmpL; j++){
            sum[i][j] += sum[i-1][j];
        }
    }

    // 众数处理
    for(int i = 1; i <= cntB; i++){
        for(int j = i; j <= cntB; j++){
            int maxM = mod[i][j-1];
            for(int k = (j-1)*sizB+1; k <= min(j*sizB, n); k++){
                if(maxM != k){
                    if((sum[j][maxM]-sum[i-1][maxM]) < (sum[j][a[k]]-sum[i-1][a[k]]) || (((sum[j][maxM]-sum[i-1][maxM]) == (sum[j][a[k]]-sum[i-1][a[k]]))&&(a[k] < maxM))){
                        maxM = a[k];
                    }
                }
            }
            mod[i][j] = maxM;
        }
    }

} // 预处理离散化 + 前缀和 + 众数

int Query(int l, int r){
    int ans = 0;

    if(blk[r] - blk[l] <= 1){
        for(int i = l; i <= r; i++){
            cntCol[a[i]] += 1;
        }
        for(int i = l; i <= r; i++){
            if(cntCol[a[i]] > cntCol[ans] || (cntCol[a[i]] == cntCol[ans] && a[i] < ans)){
                ans = a[i];
            }
        }
        for(int i = l; i <= r; i++){
            cntCol[a[i]] = 0;
        }
        return ans;
    } // 相邻块

    for(int i = l; i <= sizB*blk[l]; i++){
        cntCol[a[i]] += 1;
    }   
    for(int i = sizB*(blk[r]-1)+1; i <= r; i++){
        cntCol[a[i]] += 1;
    }

    ans = mod[blk[l]+1][blk[r]-1];
    for(int i = l; i <= sizB*blk[l]; i++){
        int last = sum[blk[r]-1][ans] - sum[blk[l]][ans] + cntCol[ans];
        int now  = sum[blk[r]-1][a[i]]- sum[blk[l]][a[i]]+ cntCol[a[i]];
        if(last < now || (last == now && ans > a[i])){
            ans = a[i];
        }
    }
    for(int i = sizB*(blk[r]-1)+1; i <= r; i++){
        int last = sum[blk[r]-1][ans] - sum[blk[l]][ans] + cntCol[ans];
        int now  = sum[blk[r]-1][a[i]]- sum[blk[l]][a[i]]+ cntCol[a[i]];
        if(last < now || (last == now && ans > a[i])){
            ans = a[i];
        }
    }

    for(int i = l; i <= sizB*blk[l]; i++){
        cntCol[a[i]] = 0;
    }   
    for(int i = sizB*(blk[r]-1)+1; i <= r; i++){
        cntCol[a[i]] = 0;
    }

    return ans;
}

// Main Function

int main(){
    int n, m;
    n = rd(), m = rd();
    sizB = sqrt(n);
    for(int i = 1; i <= n; i++){
        tmpLWB[i] = a[i] = rd();
        blk[i] = (i-1) / sizB + 1;      
    }

    Init(n);

    long long ans = 0; int l = 0, r = 0;
    for(int i = 1; i <= m; i++){
        l = rd(), r = rd();
        l = (l+ans-1)%n + 1, r = (r+ans-1)%n + 1;
        if(l > r) swap(l, r); // 处理答案

        ans = Query(l, r);
        ans = tmpLWB[ans]; // 防止错解的处理

        printf("%d\n", ans);  
    }

    return 0;
}