RT

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N=40007;
const int M=227;
int n,m,len,tot=0,a[N],sum[M][N],L[M],R[M],pos[N],T[N],b[N],tmp[N],last=0;
struct node{int cnt,id;}f[M][M];
int vis[N]; 
inline int query(int ql,int qr){
	int ans=0;
	if(pos[qr]-pos[ql]<=2){
		for(int i=ql;i<=qr;i++)T[b[i]]=0;
		for(int i=ql;i<=qr;i++){
			T[b[i]]++;
            if(T[b[i]]>T[ans])ans=b[i];
            else if(T[b[i]]==T[ans])ans=min(ans,b[i]);
		} 
		return a[ans];
	}
	ans=f[pos[ql]+1][pos[qr]-1].id;
	T[ans]=0,vis[ans]=0;
	for(int i=ql;i<=R[pos[ql]];i++)T[b[i]]=0,vis[b[i]]=0;
	for(int i=L[pos[qr]];i<=qr;i++)T[b[i]]=0,vis[b[i]]=0;
	for(int i=ql;i<=R[pos[ql]];i++)T[b[i]]++;
	for(int i=L[pos[qr]];i<=qr;i++)T[b[i]]++;
	int mx=0,id=0;
	for(int i=ql;i<=R[pos[ql]];i++){
		if(!vis[b[i]]){
			vis[b[i]]=1;
			int res=sum[pos[qr]-1][b[i]]-sum[pos[ql]][b[i]]+T[b[i]];
			if(res>mx){
				mx=res;
				id=b[i];
			}else if(res==mx)id=min(id,b[i]);
		}
	}
	for(int i=L[pos[qr]];i<=qr;i++){
		if(!vis[b[i]]){
			vis[b[i]]=1;
			int res=sum[pos[qr]-1][b[i]]-sum[pos[ql]][b[i]]+T[b[i]];
			if(res>mx){
				mx=res;
				id=b[i];
			}else if(res==mx)id=min(id,b[i]);
		}
	}
	int X=T[ans]+f[pos[ql]+1][pos[qr]-1].cnt;
	if(mx>X)ans=id;
	else if(mx==X)ans=min(ans,id);
	return a[ans];
}
signed main(){
	cin>>n>>m;
	len=sqrt(n);
	tot=(n-1)/len+1;
	for(int i=1;i<=n;i++)cin>>a[i],pos[i]=(i-1)/len+1,b[i]=a[i],tmp[i]=a[i];
	sort(tmp+1,tmp+n+1);
	int GG=unique(tmp+1,tmp+n+1)-(tmp+1);
	for(int i=1;i<=n;i++)b[i]=lower_bound(tmp+1,tmp+GG+1,b[i])-tmp;
//	for(int i=1;i<=n;i++)cout<<b[i]<<" ";cout<<"\n";
	for(int i=1;i<=tot;i++)L[i]=R[i-1]+1,R[i]=i*len;
	R[tot]=n;
	for(int i=1;i<=tot;i++){
	    memset(T,0,sizeof(T));node res={0,0};
		for(int j=i;j<=tot;j++){
			for(int k=L[j];k<=R[j];k++){
				T[b[k]]++;
			    if(T[b[k]]>res.cnt){
					res.cnt=T[b[k]];
					res.id=b[k];
			    }else if(T[b[k]]==res.cnt)res.id=min(b[k],res.id);
			}
			f[i][j]=res;
	    }
	}
	for(int i=1;i<=tot;i++){
		for(int j=1;j<=n;j++)sum[i][b[j]]=sum[i-1][b[j]];
		for(int j=L[i];j<=R[i];j++)sum[i][b[j]]++;
	}
	memset(T,0,sizeof(T));
	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);
		last=query(l,r);
		cout<<last<<"\n";
	}
}