In the i-th query, you are given two integers li and ri. Consider the subsequence a_{l_i},a_{l_(i+1)},a_{l_(i+2)},⋯,a_ri.

We can denote the positions(the positions according to the original sequence) where an integer appears first in this subsequence as p⁽ⁱ⁾₁,p⁽ⁱ⁾₂,⋯,p⁽ⁱ⁾_{k_i} (in ascending order, i.e.,p⁽ⁱ⁾₁<p⁽ⁱ⁾₂<⋯<p⁽ⁱ⁾_{k_i}).

Note that k_i is the number of different integers in this subsequence. You should output p⁽ⁱ⁾_⌈ki/2⌉for the i-th query.

Each test case starts with two integers n (n≤2×10⁵) and m (m≤2×10⁵). There are n integers in the next line, which indicate the integers in the sequence(i.e., a₁,a₂,⋯,a_n,0≤a_i≤2×10⁵).

There are two integers l_i and r_i 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 ans₁,ans₂,⋯,ans_m. Note that for each test case ans₀=0.

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

You should output one single line for each test case.

For each test case, output one line “Case #x: p₁,p₂,⋯,p_m”, where x is the case number (starting from 1) and p₁,p₂,⋯,p_m is the answer.

Case #:

Case #:  

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <stack>

#include <vector>

#include <queue>

#include <cstring>

#include <string>

#include <map>

#include <set>

using namespace std;

const int BufferSize = 1 << 16;

char buffer[BufferSize], *Head, *Tail;

inline char Getchar() {

	if(Head == Tail) {

		int l = fread(buffer, 1, BufferSize, stdin);

		Tail = (Head = buffer) + l;

	}

	return *Head++;

}

int read() {

	int x = 0, f = 1; char c = Getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = Getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = Getchar(); }

	return x * f;

}

#define maxn 200010

#define maxnode 4000010

int ToT, sumv[maxnode], lc[maxnode], rc[maxnode];

void update(int& y, int x, int l, int r, int p) {

	sumv[y = ++ToT] = sumv[x] + 1;

	if(l == r) return ;

	int mid = l + r >> 1; lc[y] = lc[x]; rc[y] = rc[x];

	if(p <= mid) update(lc[y], lc[x], l, mid, p);

	else update(rc[y], rc[x], mid + 1, r, p);

	return ;

}

int query(int o, int l, int r, int qr) {

	if(!o) return 0;

	if(r <= qr) return sumv[o];

	int mid = l + r >> 1, ans = query(lc[o], l, mid, qr);

	if(qr > mid) ans += query(rc[o], mid + 1, r, qr);

	return ans;

}

int rt[maxn], lstp[maxn], ANS[maxn], cnt;

int len;

char Out[maxn*7];

int main() {

	int T = read();

	for(int kase = 1; kase <= T; kase++) {

		memset(lstp, 0, sizeof(lstp));

		memset(sumv, 0, sizeof(sumv));

		memset(lc, 0, sizeof(lc));

		memset(rc, 0, sizeof(rc));

		memset(rt, 0, sizeof(rt));

		ToT = 0;

		int n = read(), q = read();

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

			int v = read();

			update(rt[i], rt[i-1], 0, n, lstp[v]);

			lstp[v] = i;

		}

		cnt = 0;

		int lst = 0;

		while(q--) {

			int ql = (read() + lst) % n + 1, qr = (read() + lst) % n + 1;

			if(ql > qr) swap(ql, qr);

			int l = ql, r = qr, k = query(rt[qr], 0, n, ql - 1) - query(rt[ql-1], 0, n, ql - 1) + 1 >> 1, lval = query(rt[ql-1], 0, n, ql - 1);

			while(l < r) {

				int mid = l + r >> 1;

				if(query(rt[mid], 0, n, ql - 1) - lval < k)

					l = mid + 1;

				else r = mid;

			}

			ANS[++cnt] = lst = l;

		}

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

		len = 0;

		int num[10], cntn;

		for(int i = 1; i <= cnt; i++) {

			int tmp = ANS[i];

			if(!tmp) Out[len++] = '0';

			cntn = 0; while(tmp) num[++cntn] = tmp % 10, tmp /= 10;

			for(int j = cntn; j; j--) Out[len++] = num[j] + '0';

			if(i < cnt) Out[len++] = ' ';

		}

		Out[len] = '\0';

		puts(Out);

	}

	return 0;

}