#include <bits/stdc++.h>
using namespace std;
const double PI = acos(0) * 2;
const double EPS = 1e-8;
const long long MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;
const int oo = 1e9;
const double foo = 1e30;
template <class T>
int getbit(T s, int i) {
  return (s >> i) & 1;
}
template <class T>
T onbit(T s, int i) {
  return s | (T(1) << i);
}
template <class T>
T offbit(T s, int i) {
  return s & (~(T(1) << i));
}
template <class T>
int cntbit(T s) {
  return __builtin_popcounll(s);
}
template <class T>
T sqr(T x) {
  return x * x;
}
inline void addmod(int& a, int val, int p = MOD) {
  if ((a = (a + val)) >= p) a -= p;
}
inline void submod(int& a, int val, int p = MOD) {
  if ((a = (a - val)) < 0) a += p;
}
inline int mult(int a, int b, int p = MOD) { return (long long)a * b % p; }
const int MAXM = 5000000 + 10;
struct Node {
  Node *l, *r;
  int L, R, cnt;
  Node();
} mem[MAXM], *nil = mem + MAXM - 1;
Node::Node() {
  l = r = nil;
  L = R = -1;
  cnt = 0;
}
Node* alloc() {
  static int cur = 0;
  return mem + (cur++);
}
Node* build(int L, int R) {
  Node* node = alloc();
  node->L = L;
  node->R = R;
  if (L == R) return node;
  node->l = build(L, (L + R) >> 1);
  node->r = build(((L + R) >> 1) + 1, R);
  return node;
}
Node* update(Node* node, int i, int val) {
  if (node->L > i || node->R < i) return node;
  Node* x = alloc();
  x->L = node->L;
  x->R = node->R;
  x->l = node->l;
  x->r = node->r;
  if (node->L == node->R) {
    x->cnt = node->cnt + val;
    return x;
  }
  x->l = update(x->l, i, val);
  x->r = update(x->r, i, val);
  x->cnt = x->l->cnt + x->r->cnt;
  return x;
}
int query(Node* node, int L, int R) {
  if (node->L > R || node->R < L) return 0;
  if (node->L >= L && node->R <= R) return node->cnt;
  return query(node->l, L, R) + query(node->r, L, R);
}
Node* root[MAXN];
vector<int> mm[MAXN];
int q, n, k;
int main() {
  scanf("%d%d", &n, &k);
  root[0] = build(0, MAXN - 1);
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    if (((int)(mm[x]).size()) >= k) {
      Node* tmp = update(root[i], mm[x][((int)(mm[x]).size()) - k], -1);
      root[i + 1] = update(tmp, i, 1);
    } else {
      root[i + 1] = update(root[i], i, 1);
    }
    mm[x].push_back(i);
  }
  int last = 0;
  scanf("%d", &q);
  for (int i = 0; i < q; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    l = (l + last) % n + 1;
    r = (r + last) % n + 1;
    if (l > r) swap(l, r);
    l--;
    r--;
    int ans = query(root[r + 1], l, r);
    printf("%d\n", ans);
    last = ans;
  }
}
