1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 3 using namespace std;
 4 typedef long long ll;
 5 
 6 const int N=1e5+7;
 7 
 8 struct node{int l,r,sum;}T[N*40];
 9 int root[N],a[N],hd[N],cnt,ct[N];
10 vector<int>Q[N];
11 int n,k,q,l,r;
12 
13 void update(int l,int r,int &x,int y,int pos,int v)
14 {
15     T[x=++cnt]=T[y],T[cnt].sum+=v;
16     if(l==r)return;
17     int mid=(l+r)>>1;
18     if(mid>=pos)update(l,mid,T[x].l,T[y].l,pos,v);
19     else update(mid+1,r,T[x].r,T[y].r,pos,v);
20 }
21 
22 int query(int l,int r,int L,int R,int rt)
23 {
24     if(L<=l&&r<=R)return T[rt].sum;
25     int mid=l+r>>1,an=0;
26     if(L<=mid)an+=query(l,mid,L,R,T[rt].l);
27     if(R>mid)an+=query(mid+1,r,L,R,T[rt].r);
28     return an;
29 }
30 
31 int main()
32 {
33     scanf("%d%d",&n,&k);
34     F(i,1,n)scanf("%d",a+i);
35     F(i,1,n)
36     {
37         update(1,n,root[i],root[i-1],i,1);
38         Q[a[i]].push_back(i);
39         if(ct[a[i]]==k)
40         {
41             int x=Q[a[i]][hd[a[i]]++];
42             update(1,n,root[i],root[i],x,-1);
43         }else ct[a[i]]++;
44     }
45     int ans=0;
46     scanf("%d",&q);
47     while(q--)
48     {
49         scanf("%d%d",&l,&r);
50         l=(l+ans)%n+1,r=(r+ans)%n+1;
51         if(l>r)swap(l,r);
52         printf("%d\n",ans=query(1,n,l,r,root[r]));
53     }
54     return 0;
55 }