#include<bits/stdc++.h>
using namespace std;
#define up(i,l,r) for(int i=(l);i<=(r);++i)
#define dn(i,l,r) for(int i=(l);i>=(r);--i)
const int N=40005;
const int K=800;
int len,bel[N],lk[K],rk[K],out[N],m,lst=0,s[K][N],mxt[K][K],n,q;
int mp[N],tim[K][K],a[N],li[N],l,r;
bool vs[N];
struct fk{
	inline void init(){
		len=sqrt(n);
		up(i,1,n) bel[i]=(i-1)/len+1;
		up(i,1,n) rk[bel[i]]=i;
		dn(i,n,1) lk[bel[i]]=i;
		up(i,1,len){
			up(j,1,m) s[i][j]=s[i-1][j];
			up(j,lk[i],rk[i]){
				++s[i][a[j]];
			}
		}
		up(i,1,len){
			int mxn=0;
			fill(mp+1,mp+m+1,0); 
			up(k,lk[i],n){
				++mp[a[k]];
				if(mp[a[k]]>mp[mxn]){
					mxn=a[k];
				}else if(mp[a[k]]==mp[mxn]){
					if(a[k]<mxn){
						mxn=a[k];
					}
				}
				mxt[i][bel[k]]=mxn;
				tim[i][bel[k]]=mp[mxn];
			}
		}
//		up(i,1,len){
//			up(j,i,len){
////				cout<<"众数:"<<i<<' '<<j<<' '<<mxt[i][j]<<'\n';
//			}
//		}
		return;
	}
	inline int query(int l,int r){
		int ans=0;mp[0]=0;
		if(bel[r]-bel[l]<=2){
			up(i,l,r) mp[a[i]]=0;
			up(i,l,r){
				++mp[a[i]];
				if((mp[a[i]]>mp[ans])||((mp[a[i]]==mp[ans])&&(a[i]<ans))){
					ans=a[i];
				}
			}
			return out[ans];
		}
		up(i,l,rk[bel[l]]) mp[a[i]]=0,vs[a[i]]=0;
		dn(i,r,lk[bel[r]]) mp[a[i]]=0,vs[a[i]]=0;
		mp[mxt[bel[l]+1][bel[r]-1]]=0;vs[mxt[bel[l]+1][bel[r]-1]]=0;
		mp[mxt[bel[l]+1][bel[r]-1]]=0;
		up(i,l,rk[bel[l]]) mp[a[i]]++;
		dn(i,r,lk[bel[r]]) mp[a[i]]++;
		mp[mxt[bel[l]+1][bel[r]-1]]+=tim[bel[l]+1][bel[r]-1];vs[mxt[bel[l]+1][bel[r]-1]]=1;
		up(i,l,rk[bel[l]]){
			if(!vs[a[i]]){
				mp[a[i]]+=s[bel[r]-1][a[i]]-s[bel[l]][a[i]];vs[a[i]]=1;
			}
		}
		dn(i,r,lk[bel[r]]){
			if(!vs[a[i]]){
				mp[a[i]]+=s[bel[r]-1][a[i]]-s[bel[l]][a[i]];vs[a[i]]=1;
			}
		}
		up(i,l,rk[bel[l]]){
			if(mp[a[i]]>mp[ans]){
				ans=a[i];
			}else if((mp[a[i]]==mp[ans])&&(a[i]<ans)){
				ans=a[i];
			}
		}
		dn(i,r,lk[bel[r]]){
			if(mp[a[i]]>mp[ans]){
				ans=a[i];
			}else if((mp[a[i]]==mp[ans])&&(a[i]<ans)){
				ans=a[i];
			}
		}
		if((mp[mxt[bel[l]+1][bel[r]-1]]>mp[ans])||((mp[mxt[bel[l]+1][bel[r]-1]]==mp[ans])&&(mxt[bel[l]+1][bel[r]-1]<ans))){
			ans=mxt[bel[l]+1][bel[r]-1];
		}
		return out[ans];
	}
}bit;
int main(){
//	freopen("P4168_1.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>q;
	up(i,1,n){
		cin>>a[i];li[i]=a[i];
	}
	sort(li+1,li+n+1);
	m=unique(li+1,li+n+1)-li-1;
	up(i,1,m) out[i]=li[i];
	up(i,1,n) a[i]=lower_bound(li+1,li+m+1,a[i])-li;
	bit.init();
	up(i,1,q){
		cin>>l>>r;
		l=((l+lst-1)%n)+1;r=((r+lst-1)%n)+1;
		if(l>r) swap(l,r);
		lst=bit.query(l,r);
		cout<<lst<<'\n';
	}
	return 0;
}
//tomxi