Sequence II

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a); i <= (b); ++ i)
#define per(i, a, b) for(int i = (a); i >= (b); -- i)
#define pb emplace_back
#define All(X) X.begin(), X.end()
using namespace std;
using ll = long long;

struct Node {
	int l, r, v;
};

void solve(int T) { cout << "Case #" << T << ": ";
	int n, m; cin >> n >> m;
	vector<int> a(n + 1), nums;
	rep(i, 1, n) cin >> a[i], nums.pb(a[i]);
	sort(All(nums));
	nums.erase(unique(All(nums)), nums.end());
	rep(i, 1, n) a[i] = lower_bound(All(nums), a[i]) - nums.begin() + 1;
	vector<Node> t(n * 50, {0, 0, 0});
	int idx = 0;
	function<int(int, int)> build = [&](int l, int r) {
		int x = ++ idx;
		if(l == r) return x;
		int mid = l + r >> 1;
		t[x].l = build(l, mid), t[x].r = build(mid + 1, r);
		return x;
	};
	vector<int> root(n + 2, 0);
	root[n + 1] = build(1, n);
	vector<int> mp(n + 1, 0);
	function<int(int, int, int, int, int)> update = [&](int y, int l, int r, int p, int v) {
		int x = ++ idx;
		t[x] = t[y];
		if(l == r) {
			t[x].v = v;
			return x;
		}
		int mid = l + r >> 1;
		if(p <= mid) t[x].l = update(t[y].l, l, mid, p, v);
		else t[x].r = update(t[y].r, mid + 1, r, p, v);
		t[x].v = t[t[x].l].v + t[t[x].r].v;
		return x;
	};
	function<int(int, int, int, int, int)> query = [&](int x, int l, int r, int L, int R) {
		if(L <= l && r <= R) return t[x].v;
		int ret = 0;
		int mid= l + r >> 1;
		if(L <= mid) ret += query(t[x].l, l, mid, L, R);
		if(R > mid) ret += query(t[x].r, mid + 1, r, L, R);
		return ret;
	};
	function<int(int, int, int, int)> find = [&](int x, int l, int r, int v) {
		if(l == r) return l;
		int mid= l + r >> 1;
		if(t[t[x].l].v >= v) return find(t[x].l, l, mid, v);
		else return find(t[x].r, mid + 1, r, v - t[t[x].l].v);
	};
	per(i, n, 1) {
		root[i] = update(root[i + 1], 1, n, i, 1);
		if(mp[a[i]]) root[i] = update(root[i], 1, n, mp[a[i]], 0);
		mp[a[i]] = i;
	}
	int pre = 0;
	rep(i, 1, m) {
		int l, r; cin >> l >> r;
		l = (l + pre) % n + 1, r = (r + pre) % n + 1;
		int k = query(root[l], 1, n, l, r);
		cout << (pre = find(root[l], 1, n, (k + 1) >> 1)) << ' ';
	} cout << '\n';
}

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int T = 1; cin >> T;
	rep(i, 1, T) solve(i);
	return 0;
}