Problem Description

Mr. Frog has an integer sequence of length n, which can be denoted as a1,a2,⋯,an There are m queries.

In the i-th query, you are given two integers li and ri. Consider the subsequence ali,ali+1,ali+2,⋯,ari.

We can denote the positions(the positions according to the original sequence) where an integer appears first in this subsequence as p(i)1,p(i)2,⋯,p(i)ki (in ascending order, i.e.,p(i)1<p(i)2<⋯<p(i)ki).

Note that ki is the number of different integers in this subsequence. You should output p(i)⌈ki2⌉for the i-th query.

 

Input

In the first line of input, there is an integer T (T≤2) denoting the number of test cases.

Each test case starts with two integers n (n≤2×105) and m (m≤2×105). There are n integers in the next line, which indicate the integers in the sequence(i.e., a1,a2,⋯,an,0≤ai≤2×105).

There are two integers li and ri in the following m lines.

However, Mr. Frog thought that this problem was too young too simple so he became angry. He modified each query to l‘i,r‘i(1≤l‘i≤n,1≤r‘i≤n). As a result, the problem became more exciting.

We can denote the answers as ans1,ans2,⋯,ansm. Note that for each test case ans0=0.

You can get the correct input li,ri from what you read (we denote them as l‘i,r‘i)by the following formula:

 

Output

You should output one single line for each test case.

For each test case, output one line “Case #x: p1,p2,⋯,pm”, where x is the case number (starting from 1) and p1,p2,⋯,pm is the answer.

 

Sample Input

 

Sample Output

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <cstdlib>

#include <sstream>

#include <cstring>

#include <bitset>

#include <string>

#include <deque>

#include <stack>

#include <cmath>

#include <queue>

#include <set>

#include <map>

using namespace std;

#define INF 0x3f3f3f3f

#define CLR(arr,val) memset(arr,val,sizeof(arr))

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

typedef pair<int,int> pii;

typedef long long LL;

const double PI=acos(-1.0);

const int N=2e5+7;

struct seg

{

    int lson,rson;

    int cnt;

    inline void init()

    {

        lson=rson=cnt=0;

    }

};

seg T[N*40];

int root[N],tot;

int arr[N],ans[N],pre[N];

void init(int n)

{

    CLR(root,0);

    tot=0;

    T[n+1].init();

    ans[0]=0;

    CLR(pre,-1);

}

inline void update(int &cur,int ori,int l,int r,int pos,int v)

{

    cur=++tot;

    T[cur]=T[ori];

    T[cur].cnt+=v;

    if(l==r)

        return ;

    int mid=MID(l,r);

    if(pos<=mid)

        update(T[cur].lson,T[ori].lson,l,mid,pos,v);

    else

        update(T[cur].rson,T[ori].rson,mid+1,r,pos,v);

}

int query(int S,int E,int l,int r,int ql,int qr)

{

    if(ql<=l&&r<=qr)

        return T[E].cnt-T[S].cnt;

    else

    {

        int mid=MID(l,r);

        if(qr<=mid)

            return query(T[S].lson,T[E].lson,l,mid,ql,qr);

        else if(ql>mid)

            return query(T[S].rson,T[E].rson,mid+1,r,ql,qr);

        else

            return query(T[S].lson,T[E].lson,l,mid,ql,mid)+query(T[S].rson,T[E].rson,mid+1,r,mid+1,qr);

    }

}

int findkth(int S,int E,int l,int r,int k)

{

    if(l==r)

        return l;

    else

    {

        int cnt=T[T[E].lson].cnt-T[T[S].lson].cnt;

        int mid=MID(l,r);

        if(k<=cnt)

            return findkth(T[S].lson,T[E].lson,l,mid,k);

        else

            return findkth(T[S].rson,T[E].rson,mid+1,r,k-cnt);

    }

}

int main(void)

{

    int tcase,n,m,i,l,r,L,R;

    scanf("%d",&tcase);

    for (int q=1; q<=tcase; ++q)

    {

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

        init(n);

        for (i=1; i<=n; ++i)

            scanf("%d",&arr[i]);

        int temp_rt=0;

        for (i=1; i<=1; ++i)

        {

            if(pre[arr[i]]==-1)

                update(root[i],root[i+1],1,n,i,1);

            else

            {

                update(temp_rt,root[i+1],1,n,pre[arr[i]],-1);

                update(root[i],temp_rt,1,n,i,1);

            }

            pre[arr[i]]=i;

        }

        for (i=1; i<=m; ++i)

        {

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

            L=(l+ans[i-1])%n+1;

            R=(r+ans[i-1])%n+1;

            if(L>R)

                swap(L,R);

            int D=query(root[n+1],root[L],1,n,L,R);

            ans[i]=findkth(root[n+1],root[L],1,n,(D+1)/2);

        }

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

        for (i=1; i<=m; ++i)

            printf(" %d",ans[i]);

        putchar('\n');

    }

    return 0;

}