#include <bits/stdc++.h>
using namespace std;
struct Node {
  int val;
  Node() {}
  Node(int val) : val(val) {}
  Node operator+(const Node& rhs) const {
    Node ret;
    ret.val = this->val + rhs.val;
    return ret;
  }
};
int T = 0;
int root[100005];
Node seg[7000005];
int leftC[7000005];
int rightC[7000005];
void build(int p, int l, int r) {
  if (l == r) {
    seg[p].val = 0;
    return;
  }
  leftC[p] = T++;
  rightC[p] = T++;
  int mid = (l + r) / 2;
  build(leftC[p], l, mid);
  build(rightC[p], mid + 1, r);
  seg[p] = seg[leftC[p]] + seg[rightC[p]];
}
int update(int l, int r, int s, int e, int p, int val) {
  if (r < s || l > e) return p;
  int newp = T++;
  seg[newp] = seg[p];
  leftC[newp] = leftC[p];
  rightC[newp] = rightC[p];
  if (s <= l && r <= e) {
    seg[newp].val = val;
    return newp;
  }
  int mid = (l + r) / 2;
  leftC[newp] = update(l, mid, s, e, leftC[newp], val);
  rightC[newp] = update(mid + 1, r, s, e, rightC[newp], val);
  seg[newp] = seg[leftC[newp]] + seg[rightC[newp]];
  return newp;
}
Node query(int l, int r, int s, int e, int p) {
  if (l > e || r < s) return Node(0);
  if (s <= l && r <= e) return seg[p];
  int mid = (l + r) / 2;
  Node q1 = query(l, mid, s, e, leftC[p]);
  Node q2 = query(mid + 1, r, s, e, rightC[p]);
  return q1 + q2;
}
int n, k;
long long a[100005];
set<int> se[100005];
int main() {
  ios::sync_with_stdio(0);
  cin >> n >> k;
  root[0] = T++;
  build(root[0], 1, n);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    se[a[i]].insert(i);
    root[i] = update(1, n, i, i, root[i - 1], 1);
    if (se[a[i]].size() > k) {
      int idx = *se[a[i]].begin();
      se[a[i]].erase(se[a[i]].begin());
      root[i] = update(1, n, idx, idx, root[i], 0);
    }
  }
  int q;
  cin >> q;
  long long last = 0;
  while (q--) {
    long long l, r;
    cin >> l >> r;
    l = ((l + last) % n) + 1;
    r = ((r + last) % n) + 1;
    if (l > r) swap(l, r);
    Node ans = query(1, n, l, r, root[r]);
    cout << ans.val << endl;
    last = ans.val;
  }
  return 0;
}
