#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n, k, a[maxn], prv[maxn], last = 0, ans = 0, l, r, q;
vector<int> pos[maxn];
vector<vector<int> > v;
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cin >> n >> k;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < n; i++) {
    pos[a[i]].push_back(i);
  }
  for (int i = 0; i < maxn; i++) {
    for (int j = 0; j < pos[i].size(); j++) {
      if (j < k)
        prv[pos[i][j]] = -1;
      else
        prv[pos[i][j]] = pos[i][j - k];
    }
  }
  int len = sqrt(n);
  v.resize(len + 10);
  for (int i = 0; i < n; i++) {
    v[i / len].push_back(prv[i]);
  }
  for (int i = 0; i <= len; i++) {
    sort(v[i].begin(), v[i].end());
  }
  cin >> q;
  while (q--) {
    cin >> l >> r;
    l = (l + last) % n;
    r = (r + last) % n;
    if (l > r) swap(l, r);
    ans = 0;
    for (int i = l; i <= r;) {
      if (i % len == 0 && i + len <= r) {
        ans += lower_bound(v[i / len].begin(), v[i / len].end(), l) -
               v[i / len].begin();
        i += len;
      } else {
        if (prv[i] < l) ans++;
        i++;
      }
    }
    cout << ans << '\n';
    last = ans;
  }
}
