#include <bits/stdc++.h>
using namespace std;
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}
const int INF = 1 << 29;
const int MOD = 1e9 + 7;
struct persistent_tree {
  struct node;
  using iter = vector<node>::iterator;
  struct node {
    int a, b;
    iter left, right;
    int cnt;
    void pushup() { cnt = left->cnt + right->cnt; }
  };
  vector<iter> root;
  vector<node> pool;
  iter last;
  iter _build(int a, int b) {
    iter cur = last++;
    cur->a = a;
    cur->b = b;
    cur->cnt = 0;
    if (a + 1 == b) return cur;
    cur->left = _build(a, (a + b) / 2);
    cur->right = _build((a + b) / 2, b);
    return cur;
  }
  void init(int n) {
    root.resize(n);
    int lev = 0;
    for (; (1 << lev) < n; ++lev)
      ;
    ++lev;
    pool.resize(n * (lev + 2));
    last = pool.begin();
    root[0] = _build(0, n);
  }
  void _insert(iter pre, iter& cur, int val) {
    cur = last++;
    *cur = *pre;
    if (cur->a + 1 == cur->b) {
      ++cur->cnt;
      return;
    }
    if ((cur->a + cur->b) / 2 > val) {
      _insert(pre->left, cur->left, val);
    } else {
      _insert(pre->right, cur->right, val);
    }
    cur->pushup();
  }
  void insert(int timestamp, int val) {
    _insert(root[timestamp], root[timestamp + 1], val);
  }
  int _query(iter pre, iter cur, int val) {
    if (cur->a >= val) {
      return cur->cnt - pre->cnt;
    }
    int ret = _query(pre->right, cur->right, val);
    if ((cur->a + cur->b) / 2 > val) {
      ret += _query(pre->left, cur->left, val);
    }
    return ret;
  }
  int query(int L, int R, int val) { return _query(root[L], root[R], val); }
};
const int N = 1e5 + 10;
vector<int> a[N];
int v[N];
int main() {
  int n, m, q;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    int x;
    scanf("%d", &x);
    a[x].push_back(i);
  }
  for (int i = 0; i < N; ++i) {
    if (a[i].empty()) continue;
    int len = a[i].size();
    for (int j = 0; j < len; ++j) {
      v[a[i][j]] = j + m < len ? a[i][j + m] : n;
    }
  }
  persistent_tree pt;
  pt.init(n + 1);
  for (int i = 0; i < n; ++i) {
    pt.insert(i, v[i]);
  }
  scanf("%d", &q);
  int ret = 0;
  while (q--) {
    int x, y;
    scanf("%d%d", &x, &y);
    x = (x + ret) % n;
    y = (y + ret) % n;
    if (x > y) swap(x, y);
    ++y;
    ret = pt.query(x, y, y);
    printf("%d\n", ret);
  }
  return 0;
}
