#include <bits/stdc++.h>
using namespace std;
long long q, a[555555], k, l, m, n, o, p;
const long long mod = 1e9 + 7;
queue<long long> qq[100005];
struct node {
  node *left, *right;
  long long val;
  node() {
    val = 0;
    left = right = this;
  }
  node(node *le, node *re, long long va) {
    le = left, re = right;
    val = va;
  }
};
node *ver[555555];
void build(long long s, long long e, node *r) {
  if (s == e) {
    return;
  }
  r->left = new node(NULL, NULL, 0);
  r->right = new node(NULL, NULL, 0);
  build(s, ((s + e) / 2), r->left), build(((s + e) / 2) + 1, e, r->right);
}
void update(long long s, long long e, long long id, long long val, node *r1,
            node *r2) {
  if (s > id || e < id) return;
  if (s == e) {
    r2->val = val;
    return;
  }
  if (id <= ((s + e) / 2)) {
    r2->right = r1->right;
    r2->left = new node(NULL, NULL, 0);
    update(s, ((s + e) / 2), id, val, r1->left, r2->left);
  } else {
    r2->left = r1->left;
    r2->right = new node(NULL, NULL, 0);
    update(((s + e) / 2) + 1, e, id, val, r1->right, r2->right);
  }
  r2->val = r2->left->val + r2->right->val;
}
long long query(long long s, long long e, node *r1, long long l, long long r) {
  if (l > e || s > r) return 0;
  if (l <= s && e <= r) return r1->val;
  return query(s, ((s + e) / 2), r1->left, l, r) +
         query(((s + e) / 2) + 1, e, r1->right, l, r);
}
void solve() {
  cin >> n >> m;
  ver[0] = new node();
  for (long long i = 1; i <= n; i++) cin >> a[i];
  for (long long i = 1; i <= n; i++) {
    k = a[i];
    ver[i * 2 - 1] = new node(NULL, NULL, 0);
    ver[i * 2] = new node(NULL, NULL, 0);
    update(1, n, i, 1, ver[i * 2 - 2], ver[i * 2 - 1]);
    if (qq[k].size() == m) {
      long long op = qq[k].front();
      qq[k].pop();
      update(1, n, op, 0, ver[i * 2 - 1], ver[i * 2]);
    } else
      ver[i * 2] = ver[i * 2 - 1];
    qq[k].push(i);
  }
  long long last = 0, s, e;
  cin >> l;
  while (l--) {
    cin >> s >> e;
    o = (s + last) % n + 1;
    p = (e + last) % n + 1;
    if (o > p) swap(o, p);
    last = query(1, n, ver[2 * p], o, n);
    cout << last << endl;
  }
}
int main() {
  q = 1;
  while (q--) {
    solve();
  }
}
