rt，真的快调死了

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
#define ll long long
using namespace std;
map<ll,ll> ma;
ll tot,val[100001],tr[100001];
ll buc[100001];
ll R[2501],L[2501],mxn[801][801],pos[100001];
vector<ll> ve[100001];
inline ll read(){
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
ll find_small(ll x,ll l){
	ll lef=0,rig=ve[x].size()-1;
	while(lef<rig){
		ll mid=(lef+rig)>>1;
		if(ve[x][mid]>=l) rig=mid;
		else lef=mid+1;
	}
	return lef;
}
ll find_big(ll x,ll r){
	ll lef=0,rig=ve[x].size()-1;
	while(lef<rig){
		ll mid=(lef+rig+1)>>1;
		if(ve[x][mid]<=r) lef=mid;
		else rig=mid-1;
	}
	return lef;
}
ll query(ll l,ll r){
	ll q=pos[l],p=pos[r];
	if(p-q<=1){
		ll tmp=0;
		for(ll i=l;i<=r;i++){
			buc[val[i]]++;
			if(buc[val[i]]>buc[tmp]) tmp=val[i];
		}
		for(ll i=l;i<=r;i++) buc[val[i]]=0;
		return tr[tmp];
	}
	else{
		ll ans=0,tmp=0;
		for(ll i=l;i<=R[q];i++){
			ll lef=find_small(val[i],l),rig=find_big(val[i],r);
			if(rig-lef+1>tmp){
				ans=val[i];
				tmp=rig-lef+1;
			}
		}
		ll lef=find_small(mxn[q+1][p-1],l),rig=find_big(mxn[q+1][p-1],r);
		if(rig-lef+1>tmp){
			ans=mxn[q+1][p-1];
			tmp=rig-lef+1;
		}
		for(ll i=L[p];i<=r;i++){
			ll lef=find_small(val[i],l),rig=find_big(val[i],r);
			if(rig-lef+1>tmp){
				ans=val[i];
				tmp=rig-lef+1;
			}
		}
		return tr[ans];
	}
}
ll t,n,m;
void pre(){
	for(ll i=1;i<=t;i++){
		L[i]=(i-1)*t+1;
		R[i]=i*t;
	}
	if(R[t]<n){
		t++;
		L[t]=R[t-1]+1;
		R[t]=n;
	}
	for(ll i=1;i<=t;i++)for(int j=L[i];j<=R[i];j++)pos[j]=i;
	for(ll i=1;i<=n;i++)ve[val[i]].push_back(i);
}
void do_mxn(){
	for(ll i=1;i<=t;i++){
		ll tmp=0;
		for(ll j=i;j<=t;j++){
			for(ll k=L[j];k<=R[j];k++){
				buc[val[k]]++;
				if(buc[val[k]]>buc[tmp]) tmp=val[k];
			}
			mxn[i][j]=tmp;
		}
		for(ll j=L[i];j<=n;j++) buc[val[j]]=0;
	}
}
int main(){
	ll tmp,l,r,x=0;
	n=read();m=read();
	for(ll i=1;i<=n;i++){
		tmp=read();
		if(!ma[tmp]){
			ma[tmp]=++tot;
			tr[tot]=tmp;
		}
		val[i]=ma[tmp];
	}
	t=sqrt(n);
	pre();
	do_mxn();
	for(ll i=1;i<=m;i++){
		l=read();r=read();
		l=((l+x-1)%n)+1;
		r=((r+x-1)%n)+1;
		if(l>r) swap(l,r);
		x=query(l,r);
		cout<<x<<endl;
	}
}