#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100100;
int n, k, q, a[MAXN], ans = 0, x, y, l, r;
queue<int> s[MAXN];
struct no {
  int sum;
  no *l, *r;
  no(int sum = 0) : sum(sum), l(nullptr), r(nullptr) {}
};
typedef no* noptr;
inline int getsum(noptr n) { return (n ? n->sum : 0); }
noptr upd(noptr n, int pos, int val, int beg, int end) {
  if (beg == end) return new no(val);
  noptr ret;
  int mid = (beg + end) >> 1;
  if (n)
    ret = new no(*n);
  else
    ret = new no();
  if (pos <= mid)
    ret->l = upd(ret->l, pos, val, beg, mid);
  else
    ret->r = upd(ret->r, pos, val, mid + 1, end);
  ret->sum = getsum(ret->l) + getsum(ret->r);
  return ret;
}
int get(noptr n, int a, int b, int beg, int end) {
  if (!n || b < beg || end < a) return 0;
  if (a <= beg && end <= b) return n->sum;
  int mid = (beg + end) >> 1;
  return get(n->l, a, b, beg, mid) + get(n->r, a, b, mid + 1, end);
}
noptr pseg[MAXN];
int main() {
  scanf("%d %d", &n, &k);
  pseg[0] = nullptr;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]), s[a[i]].push(i);
    pseg[i] = upd(pseg[i - 1], i, 1, 1, n);
    if (s[a[i]].size() > k) {
      pseg[i] = upd(pseg[i], s[a[i]].front(), 0, 1, n);
      s[a[i]].pop();
    }
  }
  for (scanf("%d", &q); q--;) {
    scanf("%d %d", &x, &y);
    l = ((x + ans) % n) + 1;
    r = ((y + ans) % n) + 1;
    if (l > r) swap(l, r);
    ans = get(pseg[r], l, r, 1, n);
    printf("%d\n", ans);
  }
}
