#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int a[40001];
int tmp[40001];
int she[40001];
int zf[40001];
int st[201],ed[201],bel[40001];
int f[201][201];
vector<int> dui[40001];
int last=0;
void hash_work(){
	for(int i=1;i<=n;i++)
		tmp[i]=a[i];
	sort(tmp+1,tmp+n+1);
	for(int i=1;i<=n;i++){
		int k=lower_bound(tmp+1,tmp+n+1,a[i])-tmp;
		she[k]=a[i],a[i]=k;
	}
}
void pre(int step){
	for(int i=1;i<=n;i++)
		tmp[i]=0;
	int maxx__cnt=0,maxx__ans=0;
	for(int i=st[step];i<=n;i++){
		tmp[a[i]]++;
		if(tmp[a[i]]>maxx__cnt||(tmp[a[i]]==maxx__cnt&&zf[a[i]]<zf[maxx__ans]))
			maxx__cnt=tmp[a[i]],maxx__ans=a[i];
		f[step][bel[i]]=maxx__ans;
	}
}
int cnt_sum(int l,int r,int x){
	return upper_bound(dui[x].begin(),dui[x].end(),r)-lower_bound(dui[x].begin(),dui[x].end(),l);
}
int query(int l,int r){
	if(bel[r]-bel[l]<=2){
		int maxx__cnt=0,maxx__ans=0;
		for(int i=l;i<=r;i++){
			int k=cnt_sum(l,r,a[i]);
			if(k>maxx__cnt||(k==maxx__cnt&&zf[a[i]]<zf[maxx__ans]))
				maxx__cnt=k,maxx__ans=a[i];
		}
		return maxx__ans; 
	}
	else{
		int maxx__ans=f[bel[l]+1][bel[r]-1],maxx__cnt=cnt_sum(l,r,maxx__ans);
		for(int i=l;i<=ed[bel[l]];i++){
			int k=cnt_sum(l,r,a[i]);
			if(k>maxx__cnt||(k==maxx__cnt&&zf[a[i]]<zf[maxx__ans]))
				maxx__cnt=k,maxx__ans=a[i];
		}
		for(int i=st[bel[r]];i<=r;i++){
			int k=cnt_sum(l,r,a[i]);
			if(k>maxx__cnt||(k==maxx__cnt&&zf[a[i]]<zf[maxx__ans]))
				maxx__cnt=k,maxx__ans=a[i];
		}
		return maxx__ans; 
	}
}
signed main(){
	//freopen("P4168_1.in","r",stdin);
	memset(zf,0x3f,sizeof(zf));
	cin>>n>>m;q=sqrt(n);
	for(int i=1;i<=n;i++)
		cin>>a[i];
	hash_work();
	for(int i=1;i<=n;i++)
		dui[a[i]].push_back(i),zf[a[i]]=min(zf[a[i]],i);
	for(int i=1;i<=q;i++)
		st[i]=n/q*(i-1)+1,ed[i]=n/q*i;ed[q]=n;
	for(int i=1;i<=q;i++)
		for(int j=st[i];j<=ed[i];j++)
			bel[j]=i;
	for(int i=1;i<=q;i++)
		pre(i);
	for(int i=1;i<=m;i++){
		int l,r;
		cin>>l>>r;
		l=(l+last-1)%n+1;
        r=(r+last-1)%n+1;
        if(l>r)swap(l,r);
        int ans=query(l,r);
        cout<<she[ans]<<'\n';last=she[ans];
	}
	return 0;
}