1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<map>
 7 //by NeighThorn
 8 using namespace std;
 9 
10 const int maxn=40000+5,blo=200;
11 
12 map<int,int> mp;
13 
14 vector<int> v[maxn];
15 
16 int n,m,cnt,ans,a[maxn],id[maxn],tot[maxn],val[maxn],f[200+5][200+5];
17 
18 inline void init(int x){
19     int mode=0,maxcnt=0;
20     memset(tot,0,sizeof(tot));
21     for(int i=(x-1)*blo+1;i<=n;i++){
22         tot[a[i]]++;
23         if(tot[a[i]]>maxcnt||(tot[a[i]]==maxcnt&&val[a[i]]<val[mode]))
24             mode=a[i],maxcnt=tot[a[i]];
25         f[x][id[i]]=mode;
26     }
27 }
28 
29 inline int qrycnt(int l,int r,int x){
30     return upper_bound(v[x].begin(),v[x].end(),r)-lower_bound(v[x].begin(),v[x].end(),l);
31 }
32 
33 inline int query(int l,int r){
34     int mode=f[id[l]+1][id[r]-1],maxcnt=qrycnt(l,r,mode);
35     for(int i=l;i<=min(r,id[l]*blo);i++){
36         int tmp=qrycnt(l,r,a[i]);
37         if(tmp>maxcnt||(tmp==maxcnt&&val[a[i]]<val[mode]))
38             mode=a[i],maxcnt=tmp;
39     }
40     if(id[l]!=id[r]){
41         for(int i=(id[r]-1)*blo+1;i<=r;i++){
42             int tmp=qrycnt(l,r,a[i]);
43             if(tmp>maxcnt||(tmp==maxcnt&&val[a[i]]<val[mode]))
44                 mode=a[i],maxcnt=tmp;
45         }
46     }
47     return mode;
48 }
49 
50 signed main(void){
51     ans=cnt=0;
52     scanf("%d%d",&n,&m);
53     for(int i=1;i<=n;i++){
54         scanf("%d",&a[i]);
55         if(mp.find(a[i])==mp.end())
56             mp[a[i]]=++cnt,val[cnt]=a[i];
57         a[i]=mp[a[i]];v[a[i]].push_back(i);
58     }
59     for(int i=1;i<=n;i++)
60         id[i]=(i-1)/blo+1;
61     for(int i=1;i<=id[n];i++)
62         init(i);
63     for(int i=1,x,y;i<=m;i++){
64         scanf("%d%d",&x,&y);
65         x=(x+ans-1)%n+1,y=(y+ans-1)%n+1;
66         if(x>y)
67             swap(x,y);
68         ans=val[query(x,y)];
69         printf("%d\n",ans);
70     }
71     return 0;
72 }