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

/*

hdu 5919 主席树(区间不同数的个数 + 区间第k大)

problem:

给你n个数字,和m个查询.

将[l,r]之间数第一次出现的位置信息弄成一个新的数组,然后找出其中k/2大的数.(k为位置的数量)

solve:

通过主席树能够找出[l,r]之间有多少个不同的数,然后利用再用一个查询找出第k大的即可.

(都是类似与线段树的操作, T[i]存的是[1,n]的信息, 尽管说的只是[i,n] ,只是[1,i-1]的还没更新而已.  所以查询的时候出了点问题)

hhh-2016-10-07 16:48:19

*/

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <stdio.h>

#include <cstring>

#include <vector>

#include <math.h>

#include <queue>

#include <set>

#include <map>

//#define lson  i<<1

//#define rson  i<<1|1

#define ll long long

#define clr(a,b) memset(a,b,sizeof(a))

using namespace std;

const int maxn = 200100;

const int N = maxn * 100;

template<class T> void read(T&num)

{

    char CH;

    bool F=false;

    for(CH=getchar(); CH<'0'||CH>'9'; F= CH=='-',CH=getchar());

    for(num=0; CH>='0'&&CH<='9'; num=num*10+CH-'0',CH=getchar());

    F && (num=-num);

}

int stk[70], tp;

template<class T> inline void print(T p)

{

    if(!p)

    {

        puts("0");

        return;

    }

    while(p) stk[++ tp] = p%10, p/=10;

    while(tp) putchar(stk[tp--] + '0');

    putchar('\n');

}

int lson[N],rson[N],c[N];

int a[maxn],T[maxn];

int tot,n,m;

int build(int l,int r)

{

    int root = tot++;

    c[root ] = 0;

    if(l != r)

    {

        int mid = (l+r)>>1;

        lson[root] = build(l,mid);

        rson[root] = build(mid+1,r);

    }

    return root;

}

int update(int root,int pos,int val)

{

    int newroot = tot ++ ,tmp= newroot;

    c[newroot] = c[root] + val;

    int l = 1,r = n;

    while(l < r)

    {

        int mid = (l + r) >> 1;

        if(pos <= mid)

        {

            lson[newroot] = tot++;

            rson[newroot] = rson[root];

            newroot = lson[newroot] ;

            root = lson[root];

            r = mid;

        }

        else

        {

            lson[newroot] = lson[root],rson[newroot] = tot++;

            newroot = rson[newroot],root = rson[root];

            l = mid + 1;

        }

        c[newroot] = c[root] + val;

    }

    return tmp;

}

int query(int root,int pos)

{

    int cnt = 0;

    int l = 1,r = n;

    while(pos < r)

    {

        int mid = (l + r) >> 1;

        if(pos <= mid)

        {

            root = lson[root];

            r = mid;

        }

        else

        {

            cnt += c[lson[root]];

            root = rson[root];

            l = mid + 1;

        }

    }

    return cnt + c[root];

}

int Find(int root,int k)

{

    int l = 1,r = n;

    while(l <= r)

    {

        int mid = (l + r) >> 1;

        if(l == r)

            return l;

        if(c[lson[root]] >= k)

        {

            root = lson[root];

            r = mid;

        }

        else

        {

            k -= c[lson[root]];

            root = rson[root];

            l = mid +1 ;

        }

    }

}

int main()

{

    int t,cas = 1;

//    freopen("in.txt","r",stdin);

    read(t);

    while(t--)

    {

        tot = 0;

        read(n),read(m);

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

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

        T[n + 1] = build(1,n);

        map<int,int> mp;

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

        {

            if(mp.find(a[i]) == mp.end())

            {

                T[i] = update(T[i + 1],i,1);

            }

            else

            {

                int tp = update(T[i+1],mp[a[i]],-1);

                T[i] = update(tp,i,1);

            }

            mp[a[i]] = i;

        }

        int ans = 0;

        int l,r;

        printf("Case #%d:",cas++);

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

        {

            read(l),read(r);

//            cout << l <<" " <<r << endl;

            l = (l + ans) % n + 1;

            r = (r + ans)%n + 1;

            if(l > r)

                swap(l,r);

            int num = (query(T[l],r)+1) >> 1;

//            if(!num) num = 1;

            ans = Find(T[l],num);

            printf(" %d",ans);

        }

        printf("\n");

    }

    return 0;

}