本地AC ， 提交TLE

#include<bits/stdc++.h>
//#define int long long
//#define lld d
using namespace std;
int n,m,a[1000001];
int cnt,len,bel[1000001];
unordered_map<int,int>H,ans;
struct Node{
	int l,r;
	unordered_map<int,int>s;
	vector<int>num;
}fk[10001];
int pre[351][40001],s[351][351];
int lastans;
int read(){
	int k=0;
	char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)){
		k=(k<<1)+(k<<3)+(ch^48);
		ch=getchar();
	}
	return k;
}
signed main(){
//	freopen("4168.in","r",stdin);
//	freopen("4168.out","w",stdout);
//	scanf("%d %d",&n,&m);
	n=read();m=read();
	len=sqrt(n);
	for(int i=1;i<=n;i++){
		//scanf("%d",&a[i]);
		a[i]=read();
		bel[i]=(i/len)+1;
		if(!H[a[i]]) H[a[i]]=++cnt;
		ans[H[a[i]]]=a[i];
		if(!fk[bel[i]].s[a[i]])
			fk[bel[i]].num.push_back(a[i]);
		fk[bel[i]].s[a[i]]++;
	}
	fk[bel[n]].r=n;
	
	for(int i=1;i<=bel[n];i++){
		for(int j=1;j<=cnt;j++)
			pre[i][j]=pre[i-1][j]+fk[i].s[ans[j]];
	}
	for(int i=1;i<=bel[n];i++){
		int now=0;
		unordered_map<int,int>nows;
		for(int j=i;j<=bel[n];j++){
			for(auto k:fk[j].num){
				nows[k]+=fk[j].s[k];
				now=nows[k]==nows[now]?(k>now?now:k):(nows[k]>nows[now]?k:now);
			}
			s[i][j]=now;
		}
	}

	while(m--){
		int l=read(),r=read();
		l=(l+lastans-1)%n+1;
		r=(r+lastans-1)%n+1;
		if(l>r) swap(l,r);
		int now=0;
	//	cout<<"A"<<endl;
		unordered_map<int,int>nows;
		if(bel[r]-bel[l]<=1){
	//		cout<<"C"<<endl;
			for(int i=l;i<=r;i++){
				nows[a[i]]++;
				now=nows[a[i]]==nows[now]?(a[i]>now?now:a[i]):(nows[a[i]]>nows[now]?a[i]:now);
			}
			printf("%d\n",now);
			lastans=now;
			continue;
		}	
		else{
		//	cout<<"B"<<endl;
			for(int i=l;bel[i]==bel[l];i++){
				if(!nows[a[i]])
					nows[a[i]]+=pre[bel[r]-1][H[a[i]]]-pre[bel[l]][H[a[i]]];
				nows[a[i]]++;
				now=nows[a[i]]==nows[now]?(a[i]>now?now:a[i]):(nows[a[i]]>nows[now]?a[i]:now);
			}
			for(int i=r;bel[i]==bel[r];i--){
				if(!nows[a[i]])
					nows[a[i]]+=pre[bel[r]-1][H[a[i]]]-pre[bel[l]][H[a[i]]];
				nows[a[i]]++;
				now=nows[a[i]]==nows[now]?(a[i]>now?now:a[i]):(nows[a[i]]>nows[now]?a[i]:now);
			}
			int nowk=s[bel[l]+1][bel[r]-1];
			if(!nows[nowk]){
				nows[nowk]+=(pre[bel[r]-1][H[nowk]]-pre[bel[l]][H[nowk]]);
				now=nows[nowk]==nows[now]?(nowk>now?now:nowk):(nows[nowk]>nows[now]?nowk:now);	
			}
			printf("%d\n",now);
			lastans=now;
		}
	}
//	cout<<clock()<<endl;
	return 0;
}