#include <bits/stdc++.h>
using namespace std;
const int Mx = 100005;
int N, K;
int ar[Mx];
struct persistent {
  struct node {
    int val;
    node *left, *right;
    node() {
      val = 0;
      left = nullptr;
      right = nullptr;
    }
  };
  node *version[Mx];
  void build(node *&cur, int b, int e) {
    if (b == e) {
      return;
    } else {
      int mid = (b + e) / 2;
      cur->left = new node();
      cur->right = new node();
      build(cur->left, b, mid);
      build(cur->right, mid + 1, e);
    }
  }
  void build() {
    version[0] = new node();
    build(version[0], 1, Mx - 1);
  }
  void update(node *prev, node *cur, int b, int e, int in, int val) {
    if (in < b or in > e) {
      return;
    }
    if (b == e && b == in) {
      cur->val = prev->val + val;
    } else {
      int mid = (b + e) / 2;
      if (in <= mid) {
        cur->right = prev->right;
        cur->left = new node();
        update(prev->left, cur->left, b, mid, in, val);
      } else {
        cur->left = prev->left;
        cur->right = new node();
        update(prev->right, cur->right, mid + 1, e, in, val);
      }
      cur->val = cur->left->val + cur->right->val;
    }
  }
  void update(int prev, int now, int in, int val) {
    update(version[prev], version[now], 1, Mx - 1, in, val);
  }
  void create(int in) { version[in] = new node(); }
  int query(node *cur, int b, int e, int l, int r) {
    if (l > e or r < b) return 0;
    if (b >= l and e <= r)
      return cur->val;
    else {
      int mid = (b + e) / 2;
      return query(cur->left, b, mid, l, r) +
             query(cur->right, mid + 1, e, l, r);
    }
  }
  int query(int ver, int l, int r) {
    return query(version[ver], 1, Mx - 1, l, r);
  }
} t;
deque<int> de[Mx];
void solve() {
  scanf("%d %d", &N, &K);
  for (int i = 1; i <= N; i++) {
    scanf("%d", &ar[i]);
  }
  t.build();
  for (int i = 1; i <= N; i++) {
    de[ar[i]].push_back(i);
    if (de[ar[i]].size() == K + 1) {
      int id = de[ar[i]].front();
      de[ar[i]].pop_front();
      t.create(N + 1);
      t.update(i - 1, N + 1, i, 1);
      t.create(i);
      t.update(N + 1, i, id, -1);
    } else {
      t.create(i);
      t.update(i - 1, i, i, 1);
    }
  }
  int last = 0;
  int q;
  scanf("%d", &q);
  while (q--) {
    int l, r;
    scanf("%d %d", &l, &r);
    l = (l + last) % N + 1;
    r = (r + last) % N + 1;
    if (l > r) swap(l, r);
    int val = t.query(r, l, r);
    last = val;
    printf("%d\n", val);
  }
}
int32_t main() {
  int tt;
  tt = 1;
  int cas = 1;
  while (tt--) {
    solve();
  }
}
