1 #include<cstdio>  2 #include<cmath>  3 #include<algorithm>  4 #include<cstring>  5 using namespace std;  6 int n,m,sum,sz,num[40001],l[220],r[220],plv[40001][220],mode[220][220],mplv[220][220];  7 int a[40001],en,Time[40001],x,y,ma[40001],ans;  8 struct Point{int v,p;}b[40001];  9 bool operator < (const Point &a,const Point &b){return a.v<b.v;} 10 int Res,Num;char C,CH[12]; 11 inline int G() 12 { 13     Res=0;C=‘*‘; 14     while(C<‘0‘||C>‘9‘)C=getchar(); 15     while(C>=‘0‘&&C<=‘9‘){Res=Res*10+(C-‘0‘);C=getchar();} 16     return Res; 17 } 18 inline void P(int x) 19 { 20     Num=0;if(!x){putchar(‘0‘);puts("");return;} 21     while(x>0)CH[++Num]=x%10,x/=10; 22     while(Num)putchar(CH[Num--]+48); 23     puts(""); 24 } 25 void makeblock() 26 { 27     sz=(int)sqrt((double)n); if(!sz) sz=1; 28     for(sum=1;sum*sz<n;sum++) 29       { 30         l[sum]=r[sum-1]+1; 31         r[sum]=sum*sz; 32         for(int i=l[sum];i<=r[sum];i++) num[i]=sum; 33       } 34     l[sum]=r[sum-1]+1; 35     r[sum]=n; 36     for(int i=l[sum];i<=r[sum];i++) num[i]=sum; 37 } 38 void LiSan() 39 { 40     sort(b+1,b+n+1); 41     for(int i=1;i<=n;i++) 42       { 43         if(b[i].v!=b[i-1].v) en++; 44         ma[a[b[i].p]=en]=b[i].v; 45       } 46 } 47 void makeplv() 48 { 49     for(int i=1;i<=n;i++) 50       for(int j=num[i];j<=sum;j++) 51         plv[a[i]][j]++; 52 } 53 void makemode() 54 { 55     for(int i=1;i<=sum;i++) 56       { 57         memset(Time,0,sizeof(Time)); 58         int modenow,modeplv=0; 59         for(int j=i;j<=sum;j++) 60           { 61             for(int k=l[j];k<=r[j];k++) 62               { 63                 Time[a[k]]++; 64                 if(Time[a[k]]>modeplv||(Time[a[k]]==modeplv&&a[k]<modenow)) 65                   { 66                     modenow=a[k]; 67                     modeplv=Time[a[k]]; 68                   } 69               } 70             mode[i][j]=modenow; 71             mplv[i][j]=modeplv; 72           } 73       } memset(Time,0,sizeof(Time)); 74 } 75 int Getplv(const int &v,const int &L,const int &R){return plv[v][R]-plv[v][L-1];} 76 int main() 77 { 78     n=G(); m=G(); 79     for(int i=1;i<=n;i++) {b[i].v=G(); b[i].p=i;} 80     makeblock(); LiSan(); makeplv(); makemode(); 81     for(int i=1;i<=m;i++) 82       { 83         x=G(); y=G(); x=(x+ans-1)%n+1; y=(y+ans-1)%n+1; 84         if(x>y) swap(x,y); 85         int modenow,modeplv=0; 86         if(num[x]+1>=num[y]) 87           { 88             for(int j=x;j<=y;j++) 89               { 90                 Time[a[j]]++; 91                 if(Time[a[j]]>modeplv||(Time[a[j]]==modeplv&&a[j]<modenow)) 92                   { 93                     modenow=a[j]; 94                     modeplv=Time[a[j]]; 95                   } 96               } 97             for(int j=x;j<=y;j++) Time[a[j]]--; 98           } 99         else100           {101             modenow=mode[num[x]+1][num[y]-1];102             modeplv=mplv[num[x]+1][num[y]-1];103             for(int j=x;j<=r[num[x]];j++)104               {105                 Time[a[j]]++; int t=Time[a[j]]+Getplv(a[j],num[x]+1,num[y]-1);106                 if(t>modeplv||(t==modeplv&&a[j]<modenow))107                   {108                     modenow=a[j];109                     modeplv=t;110                   }111               }112             for(int j=l[num[y]];j<=y;j++)113               {114                 Time[a[j]]++; int t=Time[a[j]]+Getplv(a[j],num[x]+1,num[y]-1);115                 if(t>modeplv||(t==modeplv&&a[j]<modenow))116                   {117                     modenow=a[j];118                     modeplv=t;119                   }120               }121             for(int j=x;j<=r[num[x]];j++) Time[a[j]]--;122             for(int j=l[num[y]];j<=y;j++) Time[a[j]]--;123           }124         P(ans=ma[modenow]);125       }126     return 0;127 }