#include <bits/stdc++.h>
using namespace std;
inline int readInt() {
  int n = 0, ch = getchar();
  while (!isdigit(ch)) ch = getchar();
  while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
  return n;
}
const int MAX_N = 100000 + 3;
extern struct Node *pit, *null;
struct Node {
  Node *lc, *rc;
  int sum;
  Node() : lc(this), rc(this), sum(0) {}
  Node(int sum) : lc(null), rc(null), sum(sum) {}
  Node(Node *lc, Node *rc, int sum) : lc(lc), rc(rc), sum(sum) {}
  Node *add(int l, int r, int pos, int val) const {
    if (r - l == 1) return new (pit++) Node(sum + val);
    if (pos < (((l) + (r)) >> 1))
      return new (pit++)
          Node(lc->add(l, (((l) + (r)) >> 1), pos, val), rc, sum + val);
    else
      return new (pit++)
          Node(lc, rc->add((((l) + (r)) >> 1), r, pos, val), sum + val);
  }
  int queryPrefix(int l, int r, int pos) const {
    if (l >= pos) return 0;
    if (r <= pos) return sum;
    return lc->queryPrefix(l, (((l) + (r)) >> 1), pos) +
           rc->queryPrefix((((l) + (r)) >> 1), r, pos);
  }
} pool[MAX_N * 40], *pit = pool, *null = new (pit++) Node, *root[MAX_N];
int n, k, a[MAX_N], l[MAX_N];
vector<int> pos[MAX_N];
void prepare() {
  root[n] = null;
  for (int i = n - 1; i >= 0; --i) {
    root[i] = root[i + 1];
    if (pos[a[i]].size() - l[a[i]] == k)
      root[i] = root[i]->add(0, n, pos[a[i]][l[a[i]]++], -1);
    pos[a[i]].push_back(i);
    root[i] = root[i]->add(0, n, i, 1);
  }
}
int main() {
  n = readInt(), k = readInt();
  for (int i = 0; i < n; ++i) a[i] = readInt();
  prepare();
  int q = readInt(), lastAns = 0;
  for (int i = 0; i < q; ++i) {
    int l = (readInt() + lastAns) % n + 1, r = (readInt() + lastAns) % n + 1;
    if (l > r) swap(l, r);
    --l;
    printf("%d\n", lastAns = root[l]->queryPrefix(0, n, r));
  }
  return 0;
}
