#include <bits/stdc++.h>
using namespace std;
struct node {
  int val = 0;
  node *lc = nullptr, *rc = nullptr;
  node() {}
  node(int val) : val(val) {}
  node(node *lc, node *rc) : lc(lc), rc(rc) {
    val += lc->val;
    val += rc->val;
  }
};
typedef node *pnode;
const int maxa = 1e5 + 3, maxn = 1e5 + 3;
int n, k, q;
queue<int> qu[maxa];
int prevk[maxn];
pnode roots[maxn];
int last = 0;
pnode build(int l, int r) {
  if (l == r) return new node;
  int mid = (l + r) / 2;
  return new node(build(l, mid), build(mid + 1, r));
}
pnode update(pnode p, int l, int r, int pos) {
  if (l == r) return new node(p->val + 1);
  int mid = (l + r) / 2;
  if (pos <= mid)
    return new node(update(p->lc, l, mid, pos), p->rc);
  else
    return new node(p->lc, update(p->rc, mid + 1, r, pos));
}
int query(pnode p, int l, int r, int lb, int rb) {
  if (r < lb || l > rb) return 0;
  if (l >= lb && r <= rb) return p->val;
  int mid = (l + r) / 2;
  return query(p->lc, l, mid, lb, rb) + query(p->rc, mid + 1, r, lb, rb);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    int a;
    cin >> a;
    if (qu[a].size() < k)
      prevk[i] = 0;
    else {
      prevk[i] = qu[a].front();
      qu[a].pop();
    }
    qu[a].push(i);
  }
  roots[0] = build(0, n);
  for (int i = 1; i <= n; i++) roots[i] = update(roots[i - 1], 0, n, prevk[i]);
  cin >> q;
  while (q--) {
    int x, y;
    cin >> x >> y;
    int l = (x + last) % n + 1, r = (y + last) % n + 1;
    if (l > r) swap(l, r);
    last =
        query(roots[r], 0, n, 0, l - 1) - query(roots[l - 1], 0, n, 0, l - 1);
    cout << last << "\n";
  }
}
