#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int M = 2e6 + 10;
int n, k, q;
int a[N], c[N];
int root[N], ls[M], rs[M], s[M];
int tot = 0, ans = 0;
vector<int> v[N];
void update(int &x, int y, int l, int r, int pos) {
  x = ++tot;
  ls[x] = ls[y];
  rs[x] = rs[y];
  s[x] = s[y] + 1;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (pos <= mid)
    update(ls[x], ls[y], l, mid, pos);
  else
    update(rs[x], rs[y], mid + 1, r, pos);
}
int query(int x, int y, int L, int R, int l, int r) {
  if (l >= L && r <= R) return s[y] - s[x];
  int ret = 0;
  int mid = (l + r) >> 1;
  if (L <= mid) ret += query(ls[x], ls[y], L, R, l, mid);
  if (R > mid) ret += query(rs[x], rs[y], L, R, mid + 1, r);
  return ret;
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    v[a[i]].push_back(i);
  }
  memset(c, -1, sizeof(c));
  for (int i = 1; i <= 1e5; i++) {
    for (int j = k; j < v[i].size(); j++) c[v[i][j]] = v[i][j - k];
  }
  for (int i = 1; i <= n; i++) {
    if (c[i] == -1)
      root[i] = root[i - 1];
    else
      update(root[i], root[i - 1], 1, n, c[i]);
  }
  scanf("%d", &q);
  while (q--) {
    int x, y;
    scanf("%d%d", &x, &y);
    x = (x + ans) % n + 1;
    y = (y + ans) % n + 1;
    if (x > y) swap(x, y);
    ans = y - x + 1 - query(root[x - 1], root[y], x, y, 1, n);
    printf("%d\n", ans);
  }
  return 0;
}
