#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#define inf (1<<30)
#define ll long long
using namespace std;
inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,block,cnt,lastans;
int a[40005],hash[40005],belong[40005],num[40005];
int first[205],last[205],ans[205][205];
int L[40005],R[40005];
struct data{int p,v;}d[40005];
bool my(data a,data b){return a.v<b.v||a.v==a.v&&a.p<b.p;};
int find(int x){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)>>1;
        if(hash[mid]<x)l=mid+1;
        else if(hash[mid]>x)r=mid-1;
        else return mid;
    }
}
void pre()
{
    for(int i=1;i<=n;i++)
        d[i].v=a[i],d[i].p=i;
    sort(d+1,d+n+1,my);
    for(int i=1;i<=n;i++){
        if(!L[d[i].v])L[d[i].v]=i;
        R[d[i].v]=i;
    }
    int mx,tmp;
    for(int i=1;i<=cnt;i++){
        memset(num,0,sizeof(num));mx=0;
        for(int j=first[i];j<=n;j++){
            num[a[j]]++;
            if(num[a[j]]>mx||(num[a[j]]==mx&&a[j]<tmp)){
				mx=num[a[j]];tmp=a[j];
			}
            ans[i][belong[j]]=tmp;
        }
    }
}
int findup(int l,int r,int x){
    int tmp=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(d[mid].p>x)r=mid-1;
        else {
			tmp=mid;l=mid+1;
		}
    }
    return tmp;
}
int finddown(int l,int r,int x){
    int tmp=inf;
    while(l<=r){
        int mid=(l+r)>>1;
        if(d[mid].p<x)l=mid+1;
        else {
			tmp=mid;r=mid-1;
		}
    }
    return tmp;
}
int que(int x,int y)
{
    int tmp,mx=0;
    if(belong[x]==belong[y])
        for(int i=x;i<=y;i++){
			int num=findup(L[a[i]],R[a[i]],y)-finddown(L[a[i]],R[a[i]],x)+1;
			if(num>mx||(num==mx&&a[i]<tmp))tmp=a[i],mx=num;
		}
	else {
		if(belong[x]+1<belong[y]){
		    tmp=ans[belong[x]+1][belong[y]-1];
            mx=findup(L[tmp],R[tmp],y)-finddown(L[tmp],R[tmp],x)+1;
		}
		for(int i=x;i<=last[belong[x]];i++){
			int num=findup(L[a[i]],R[a[i]],y)-finddown(L[a[i]],R[a[i]],x)+1;
			if(num>mx||(num==mx&&a[i]<tmp))tmp=a[i],mx=num;
		}    
		for(int i=first[belong[y]];i<=y;i++){
			int num=findup(L[a[i]],R[a[i]],y)-finddown(L[a[i]],R[a[i]],x)+1;
			if(num>mx||(num==mx&&a[i]<tmp))tmp=a[i],mx=num;
		}
	}
	return tmp;
}
int main(){
	freopen("numquery.in","r",stdin);
	freopen("numquery.out","w",stdout);
    n=read();m=read();
    block=(int)sqrt((double)n);
    if(n%block)cnt=n/block+1;
    else cnt=block;
    for(int i=1;i<=n;i++)belong[i]=(i-1)/block+1;
    for(int i=1;i<=cnt;i++)first[i]=block*(i-1)+1,last[i]=block*i;
    for(int i=1;i<=n;i++)a[i]=read(),hash[i]=a[i];
    sort(hash+1,hash+n+1);
    for(int i=1;i<=n;i++)a[i]=find(a[i]);
    pre();
    for(int i=1;i<=m;i++){
        int l_0=read(),r_0=read();
        int l=(l_0+lastans-1)%n+1,r=(r_0+lastans-1)%n+1;
        if(l>r)swap(l,r);
        lastans=hash[que(l,r)];
        printf("%d\n",lastans);
    }
    return 0; 
}