#include <bits/stdc++.h>
using namespace std;
const long long N = 100000 + 5, OO = 1110111110111, mod = 1000000007,
                mod2 = 998244353;
int n, m, k, las, l, r;
int a[N];
vector<int> la[N], pre(N);
struct node {
  node *l, *r;
  int sum, bad;
  node(int val) : l(nullptr), r(nullptr), sum(val), bad(0) {}
  node(node* l, node* r) : l(l), r(r), sum(0), bad(0) {
    if (l) sum += l->sum, bad += l->bad;
    if (r) sum += r->sum, bad += r->bad;
  }
};
node* build(int l, int r) {
  if (l == r) return new node(1);
  int mid = (l + r) / 2;
  return new node(build(l, mid), build(mid + 1, r));
}
int sum(node* nod, int L, int R, int l, int r) {
  if (l > R || r < L) return 0;
  if (L == R) return nod->sum;
  int mid = (L + R) / 2;
  if (l <= L && r >= R) return nod->sum;
  return sum(nod->l, L, mid, l, r) + sum(nod->r, mid + 1, R, l, r);
}
node* update(node* nod, int L, int R, int ind, int val) {
  if (L == R) return new node(val);
  int mid = (L + R) / 2;
  if (ind <= mid)
    return new node(update(nod->l, L, mid, ind, val), nod->r);
  else
    return new node(nod->l, update(nod->r, mid + 1, R, ind, val));
}
node* pres[N];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  pres[0] = build(0, N);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    la[a[i]].push_back(i);
    if (la[a[i]].size() <= m)
      pre[i] = -1;
    else
      pre[i] = la[a[i]][la[a[i]].size() - m - 1];
  }
  for (int i = 0; i < n; i++) {
    if (pre[i] == -1)
      pres[i + 1] = update(pres[i], 0, N, i, 1);
    else
      pres[i + 1] = update(pres[i], 0, N, pre[i], 0);
  }
  cin >> k;
  while (k--) {
    cin >> l >> r;
    l = (l + las) % n + 1;
    r = (r + las) % n + 1;
    if (l > r) swap(l, r);
    las = sum(pres[r], 0, N, l - 1, r - 1);
    cout << las << "\n";
  }
  return 0;
}
