#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct segtree {
  vector<vector<int> > st;
  void kc(int n) {
    vector<int> o(0);
    st.assign(4 * n, o);
  }
  void build(int i, int l, int r, int c[]) {
    if (l == r) {
      st[i].push_back(c[l]);
      return;
    }
    int mid = (l + r) >> 1;
    build(i << 1, l, mid, c);
    build(i << 1 | 1, mid + 1, r, c);
    merge(st[i << 1].begin(), st[i << 1].end(), st[i << 1 | 1].begin(),
          st[i << 1 | 1].end(), back_inserter(st[i]));
  }
  int get(int i, int l, int r, int u, int v, int val) {
    if (u > r || v < l) return 0;
    if (u <= l && r <= v) {
      int id =
          lower_bound((st[i]).begin(), (st[i]).end(), val) - st[i].begin() - 1;
      return id + 1;
    }
    int mid = (l + r) >> 1;
    return get(i << 1, l, mid, u, v, val) +
           get(i << 1 | 1, mid + 1, r, u, v, val);
  }
};
set<int> s[N];
int n, k;
int a[N], pre[N];
segtree IT;
void gogo() {
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    if (((int)(s[a[i]]).size()) < k)
      pre[i] = -1;
    else
      pre[i] = *s[a[i]].begin();
    s[a[i]].insert(i);
    if (((int)(s[a[i]]).size()) > k) s[a[i]].erase(s[a[i]].begin());
  }
  IT.kc(n);
  IT.build(1, 1, n, pre);
  int q, last = 0;
  cin >> q;
  while (q--) {
    int x, y;
    cin >> x >> y;
    int l = (x + last) % n + 1, r = (y + last) % n + 1;
    if (l > r) swap(l, r);
    last = IT.get(1, 1, n, l, r, l);
    cout << last << '\n';
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  if (fopen("sol"
            ".inp",
            "r")) {
    freopen(
        "sol"
        ".inp",
        "r", stdin);
    freopen(
        "sol"
        ".out",
        "w", stdout);
  }
  gogo();
  return 0;
}
