#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

const int N = 1e5 + 10;

const int M = 3e6 + 10;

int n, k, q;

int a[N], c[N];

int root[N], ls[M], rs[M], s[M];

int tot = 0, ans = 0;

vector <int> v[N];

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

	x = ++tot;

	ls[x] = ls[y];

	rs[x] = rs[y];

	s[x] = s[y] + 1;

	if (l == r) return;

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

	if (pos <= mid) update(ls[x], ls[y], l, mid, pos);

	else update(rs[x], rs[y], mid + 1, r, pos);

}

int query(int x, int y, int L, int R, int l, int r){

	if (l <= L && R <= r) return s[y] - s[x];

	int ret = 0;

	int mid = (L + R) >> 1;

	if (l <= mid) ret += query(ls[x], ls[y], L, mid, l, r);

	if (r >  mid) ret += query(rs[x], rs[y], mid + 1, R, l, r);

	return ret;

}

int main(){

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

	rep(i, 1, n){

		scanf("%d", a + i);

		v[a[i]].push_back(i);

	}

	memset(c, -1, sizeof c);

	rep(i, 1, 1e5){

		int et = v[i].size();

		rep(j, k, et - 1) c[v[i][j]] = v[i][j - k];

	}

	rep(i, 1, n){

		if (c[i] == -1) root[i] = root[i - 1];

		else update(root[i], root[i - 1], 1, n, c[i]);

	}

	scanf("%d", &q);

	while (q--){

		int x, y;

		scanf("%d%d", &x, &y);

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

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

		if (x > y) swap(x, y);

		printf("%d\n", ans = y - x + 1 - query(root[x - 1], root[y], 1, n, x, y));

	}

	return 0;

}