/*

给定一个n个数的序列a

每次询问区间[l,r],求出去重后区间中每个数的第一次出现的位置pi

pi构成一个新的升序，求这个新数组的中位数

要求强制在线，询问[l,r]根据上一个询问的答案进行加密，形成新的询问

t1=(l+ansi-1) % mod n + 1

t2=(r+ansi-1) % mod n + 1

l=min(t1,t2),r=max(t1,t2)

然后再进行询问即可 

先求出a[i]在序列中上一次出现的位置pre[i]

从左往右进行一次扫描，用主席树来维护区间[1,i]的中不同数字的个数

询问[l,r]：

先求出区间出现的不同数字的个数k，具体操作见SPOJ D-QUERY

要求从左往右第k/2个数，很容易想到二分，在第r棵线段树上询问[mid,r]区间不同数字出现的个数，这样的复杂度是O(q*(logn)^2)

但这种做法是错的。。

出现这种情况是因为我们所有版本的线段树的点都是向后密集的，第i个棵线段树维护a[i]及之前的数最后出现的位置 

所以只要每个版本的线段树中不同的数出现的位置能够向前密集，那么这个问题就转变成了求第k大的数

考虑如何将数据向前密集，即保存a[i]下一次出现的位置，扫到a[i]时将i+1，将下一次出现的位置-1即可

update:a[i]

    所以从右往左更新主席树,nxt[i]-1,i+1

query:[l,r]

    先在第l个版本的线段树上查询[1,r]区间的不同数字的个数l

    在第l个版本的线段树上查询[1,r]范围内的第k/2大数的下标 

可以发现这种主席树的查询其实退化成了线段树

*/

#include<bits/stdc++.h>

using namespace std;

#define maxn 200005

#define INF 0x3f3f3f3f

struct Node{int lc,rc,sum;}t[maxn*];

int n,a[maxn],rt[maxn],size,nxt[maxn],pos[maxn];

int build(int l,int r){

    int now=++size;

    t[now].lc=t[now].rc=t[now].sum=;

    if(l==r)return now;

    int mid=l+r>>;

    t[now].lc=build(l,mid);

    t[now].rc=build(mid+,r);

    return now;

}

int update(int last,int pos,int val,int l,int r){

    int now=++size;

    t[now]=t[last];t[now].sum+=val;

    if(l==r)return now;

    int mid=l+r>>;

    if(pos<=mid)t[now].lc=update(t[last].lc,pos,val,l,mid);

    else t[now].rc=update(t[last].rc,pos,val,mid+,r);

    return now;

}

int query1(int rt,int L,int R,int l,int r){//查询区间[L,R]的和

    if(L<=l && R>=r)return t[rt].sum;

    int mid=l+r>>,res=;

    if(L<=mid) res+=query1(t[rt].lc,L,R,l,mid);

    if(R>mid)res+=query1(t[rt].rc,L,R,mid+,r);

    return res;

}

int query2(int rt,int k,int l,int r){//查询线段树第k大的值

    if(l==r)return l;

    int mid=l+r>>;

    if(k<=t[t[rt].lc].sum)return query2(t[rt].lc,k,l,mid);

    else return query2(t[rt].rc,k-t[t[rt].lc].sum,mid+,r);

}

int main(){

    int T,q;cin>>T;

    for(int tt=;tt<=T;tt++){

        size=;memset(rt,,sizeof rt);

        memset(nxt,0x3f,sizeof nxt);

        memset(pos,0x3f,sizeof pos);

        scanf("%d%d",&n,&q);

        for(int i=;i<=n;i++)scanf("%d",&a[i]);

        for(int i=n;i>=;i--){

            nxt[i]=pos[a[i]];

            pos[a[i]]=i;

        }

        rt[n+]=build(,n);

        for(int i=n;i>=;i--){

            if(nxt[i]==INF)rt[i]=update(rt[i+],i,,,n);//直接在点i增加1

            else {

                int tmp=update(rt[i+],nxt[i],-,,n);

                rt[i]=update(tmp,i,,,n);

            }

        }

        printf("Case #%d:",tt);

        int ans=,l,r;

        while(q--){

            scanf("%d%d",&l,&r);

            int t1=(l+ans)%n+,t2=(r+ans)%n+;

            l=min(t1,t2),r=max(t1,t2);

            int k=query1(rt[l],,r,,n);

            ans=query2(rt[l],k/+k%,,n);//求第k个数的下标

            printf(" %d",ans);

        }

        puts("");

    }

}