记录编号	251064	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	数字查询	最终得分	100
用户昵称	dydxh	是否通过	通过
代码语言	C++	运行时间	3.312 s
提交时间	2016-04-16 19:44:48	内存使用	33.75 MiB

/*
Problem:Numquery;
Language:c++;
by dydxh;
Date:2016.04.15;
*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<utility>
#include<cstdlib>
#include<cstdio>
#include<string>
#include<vector>
#include<ctime>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define ull unsigned long long
using namespace std;
const int oo=2000000000;
const int maxn=40005;
typedef pair<int,int> Pii;
int n,m,Block,Total;
int A[maxn],C[maxn],Nex[maxn];
int S[205],T[205],Pos[maxn];
int Appear[205][maxn];
Pii Maxx[205][205];
inline int read(){
	int x=0;bool flag=false;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-') flag=true;ch=getchar();}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return flag?-x:x;
}
/*const int mod=100000;
const int Step=10000;

int Hash[maxn<<1],Num[maxn<<1],*/
int Cnt;
int Rel[maxn],B[maxn];
/*int Hasher(int x){
	int Now=x%mod;
	while(Hash[Now]!=0 && Hash[Now]!=x){
		Now+=Step;
		if(Now>=mod) Now-=mod;
	}
	if(Hash[Now]==0) Hash[Now]=x,Num[Now]=++Cnt,Rel[Cnt]=x;
	return Num[Now];
}*/
map<int,int>H;
void Split(){
	memcpy(B,A,sizeof(B));
	sort(B+1,B+1+n);
	for(int i=1;i<=n;i++)
		if(B[i]!=B[i-1]){
			//Hasher(B[i]);
			H[B[i]]=++Cnt,Rel[Cnt]=B[i];
		}
}
int Loc[maxn],Pre[maxn];
void Initialize(){
	n=read(),m=read(),Block=(int)sqrt(1.0*n);
	for(int i=1;i<=n;i++) A[i]=read(),Pos[i]=(i-1)/Block+1;
	int Pointer=0;
	for(int i=1;i<=n;i+=Block) S[++Pointer]=i;Pointer=0;
	for(int i=Block;i<=n;i+=Block) T[++Pointer]=i;T[Total]=n;
	Split();
	Total=Pos[n];
	for(int i=1;i<=n;i++) C[i]=H[A[i]];//C[i]=Hasher(A[i]);
	for(int i=1;i<=n;i++){
		Pre[i]=Loc[C[i]];
		Loc[C[i]]=i;
	}
}
int App[maxn];
void Prepare(){
	for(int i=1;i<=n;i++) Appear[Pos[i]][C[i]]++;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=Total;j++)
			Appear[j][i]+=Appear[j-1][i];
	for(int i=1;i<=n;i+=Block){
		memset(App,0,sizeof(App));
		int Digit=0,Tim=0;
		for(int j=i;j<=n;j++){
			App[C[j]]++;
			if(App[C[j]]>Tim || (App[C[j]]==Tim && Digit>C[j])) Tim=App[C[j]],Digit=C[j];
			if(Pos[j+1]!=Pos[j])
				Maxx[Pos[i]][Pos[j]]=make_pair(Digit,Tim);
		}
	}
}
int App2[maxn],Sign1[maxn],Sign2[maxn];
int Ans,Logo;
Pii Best,Maybe;
int Query(int x,int y){
	Best=make_pair(0,0);
	if(Pos[x]+1>=Pos[y]){
		++Logo;
		for(int i=x;i<=y;i++){
			if(Pre[i]<x) App[C[i]]=1;
			else App[C[i]]++;
			if(App[C[i]]>Best.second) Best=make_pair(C[i],App[C[i]]);
			if(App[C[i]]==Best.second && C[i]<Best.first) Best.first=C[i];
		}
		return Best.first;
	}
	
	int L=Pos[x]+1,R=Pos[y]-1;
	Best=Maxx[L][R];
	++Logo;
	int St=x,En=T[Pos[x]];
	for(int i=St;i<=En;i++){
		if(Pre[i]<St) App[C[i]]=1,Sign1[C[i]]=Logo;
		else App[C[i]]++;
	}
	St=S[Pos[y]],En=y;
	for(int i=St;i<=En;i++){
		if(Pre[i]<St) App2[C[i]]=1,Sign2[C[i]]=Logo;
		else App2[C[i]]++;
	}
	
	St=x,En=T[Pos[x]];
	for(int i=St;i<=En;i++){
		Maybe.first=C[i],Maybe.second=0;
		if(Sign1[C[i]]==Logo) Maybe.second+=App[C[i]];
		if(Sign2[C[i]]==Logo) Maybe.second+=App2[C[i]];
		Maybe.second+=Appear[R][C[i]]-Appear[L-1][C[i]];
		if(Maybe.second>Best.second) Best=Maybe;
		if(Maybe.second==Best.second && Maybe.first<Best.first) Best=Maybe;
	}
	St=S[Pos[y]],En=y;
	for(int i=St;i<=En;i++){
		Maybe.first=C[i],Maybe.second=0;
		if(Sign1[C[i]]==Logo) Maybe.second+=App[C[i]];
		if(Sign2[C[i]]==Logo) Maybe.second+=App2[C[i]];
		Maybe.second+=Appear[R][C[i]]-Appear[L-1][C[i]];
		if(Maybe.second>Best.second) Best=Maybe;
		if(Maybe.second==Best.second && Maybe.first<Best.first) Best=Maybe;
	}
	return Best.first;
}
int main(){
	//freopen("cc.in","r",stdin);
	freopen("numquery.in","r",stdin);
	freopen("numquery.out","w",stdout);
	Initialize();
	Prepare();
	while(m--){
		int x=(read()+Ans-1)%n+1,y=(read()+Ans-1)%n+1;
		if(x>y) swap(x,y);
		Ans=Rel[Query(x,y)];
		printf("%d\n",Ans);
	}
	//cout<<"Time has passed:"<<1.0*clock()/1000<<"s!"<<endl;
    return 0;
}