#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, k, last = 0, q, x, y, l, r;
int a[N];
struct node {
  int s, e;
  node *l, *r;
  vector<int> b;
  node(int *from, int *to, int lo, int hi) {
    s = lo, e = hi;
    if (s == e || from >= to) return;
    int md = (s + e) >> 1;
    auto f = [md](int x) { return x <= md; };
    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 node(from, pivot, s, md);
    r = new node(pivot, to, md + 1, e);
  }
  int get_kth(int l, int r, int k) {
    if (r > l) return 0;
    if (s == e) return s;
    int inlft = b[r] - b[l - 1];
    int lb = b[l - 1];
    int rb = b[r];
    if (k <= inlft) return this->l->get_kth(lb, rb, k);
    return this->r->get_kth(l - lb, r - rb, k - inlft);
  }
  int LTE(int l, int r, int k) {
    if (l > r || s > k) return 0;
    if (e <= k) return (r - l + 1);
    int lb = b[l - 1], rb = b[r];
    return this->l->LTE(lb + 1, rb, k) + this->r->LTE(l - lb, r - rb, k);
  }
};
vector<int> idx[N];
int main() {
  scanf("%d%d", &n, &k);
  int mx = 0;
  fill(a + 1, a + n + 1, n + 1);
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    idx[x].push_back(i);
    if (idx[x].size() > k) a[idx[x][idx[x].size() - k - 1]] = i - 1;
  }
  node root(a + 1, a + n + 1, 1, N);
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d", &x, &y);
    l = (x + last) % n + 1;
    r = (y + last) % n + 1;
    if (l > r) swap(l, r);
    last = r - l + 1 - root.LTE(l, r, r - 1);
    printf("%d\n", last);
  }
}
