#include <bits/stdc++.h>
using namespace std;
const long long int N = 300009;
const long long int mod = 1000000007;
struct wavelet_tree {
  long long int lo, hi;
  wavelet_tree *l, *r;
  vector<long long int> b;
  wavelet_tree(long long int* from, long long int* to, long long int x,
               long long int y) {
    lo = x, hi = y;
    if (lo == hi or from >= to) return;
    long long int mid = (lo + hi) / 2;
    auto f = [mid](long long int x) { return x <= mid; };
    b.reserve(to - from + 1);
    b.push_back(0);
    for (auto it = from; it != to; it++) b.push_back(b.back() + f(*it));
    auto pivot = stable_partition(from, to, f);
    l = new wavelet_tree(from, pivot, lo, mid);
    r = new wavelet_tree(pivot, to, mid + 1, hi);
  }
  long long int kth(long long int l, long long int r, long long int k) {
    if (l > r) return 0;
    if (lo == hi) return lo;
    long long int inLeft = b[r] - b[l - 1];
    long long int lb = b[l - 1];
    long long int rb = b[r];
    if (k <= inLeft) return this->l->kth(lb + 1, rb, k);
    return this->r->kth(l - lb, r - rb, k - inLeft);
  }
  long long int LTE(long long int l, long long int r, long long int k) {
    if (l > r or k < lo) return 0;
    if (hi <= k) return r - l + 1;
    long long int lb = b[l - 1], rb = b[r];
    return this->l->LTE(lb + 1, rb, k) + this->r->LTE(l - lb, r - rb, k);
  }
  long long int count(long long int l, long long int r, long long int k) {
    if (l > r or k < lo or k > hi) return 0;
    if (lo == hi) return r - l + 1;
    long long int lb = b[l - 1], rb = b[r], mid = (lo + hi) / 2;
    if (k <= mid) return this->l->count(lb + 1, rb, k);
    return this->r->count(l - lb, r - rb, k);
  }
  ~wavelet_tree() {
    delete l;
    delete r;
  }
};
void pre() {}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin.exceptions(cin.failbit);
  ;
  pre();
  long long int n, k;
  cin >> n >> k;
  long long int a[n + 1];
  for (long long int i = 1; i < (n + 1); ++i) cin >> a[i];
  map<long long int, vector<long long int> > last;
  long long int b[n + 1];
  for (long long int i = 1; i < (n + 1); ++i) {
    last[a[i]].push_back(i);
    if ((long long int)((last[a[i]]).size()) > k) {
      b[i] = last[a[i]][(long long int)((last[a[i]]).size()) - (k + 1)];
    } else {
      b[i] = 0;
    }
  }
  struct wavelet_tree* X = new wavelet_tree(b + 1, b + n + 1, 0, n);
  long long int q, x, y, l, r, lst = 0;
  cin >> q;
  while (q--) {
    cin >> x >> y;
    l = (x + lst) % n + 1;
    r = (y + lst) % n + 1;
    if (l > r) swap(l, r);
    lst = X->LTE(l, r, l - 1);
    cout << lst << "\n";
  }
  return 0;
}
