#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5;
struct node {
  node *l, *r;
  int v = 0;
  node(int val) {
    l = NULL;
    r = NULL;
    v = val;
  }
  node(node* left, node* right) {
    l = left;
    r = right;
    v = 0;
    if (l) v += l->v;
    if (r) v += r->v;
  }
} * roots[MAX];
node* update(node* cur, int lo, int hi, int loc, int v) {
  if (lo == hi) return new node(v);
  int mid = (lo + hi) / 2;
  if (loc <= mid)
    return new node(update((cur ? cur->l : NULL), lo, mid, loc, v),
                    (cur ? cur->r : NULL));
  else
    return new node((cur ? cur->l : NULL),
                    update((cur ? cur->r : NULL), mid + 1, hi, loc, v));
}
int query(node* cur, int lo, int hi, int i, int j) {
  if (j < lo or hi < i or !cur) return 0;
  if (i <= lo and hi <= j) return cur->v;
  int mid = (lo + hi) / 2;
  return query(cur->l, lo, mid, i, j) + query(cur->r, mid + 1, hi, i, j);
}
vector<int> ind[MAX];
int main() {
  int n, k;
  cin >> n >> k;
  int arr[n];
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
    ind[arr[i]].emplace_back(i);
    roots[i + 1] = update(roots[i], 0, n - 1, i, 1);
    if (ind[arr[i]].size() > k)
      roots[i + 1] = update(roots[i + 1], 0, n - 1,
                            ind[arr[i]][ind[arr[i]].size() - k - 1], 0);
  }
  int q;
  cin >> q;
  int last = 0;
  for (int i = 0; i < q; i++) {
    int xi, yi;
    cin >> xi >> yi;
    int l = (xi + last) % n + 1;
    int r = (yi + last) % n + 1;
    if (l > r) swap(l, r);
    last = query(roots[r], 0, n - 1, l - 1, r - 1);
    cout << last << endl;
  }
}
