#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-6;
const int MAXN = 100005;
const int MAXM = 5005;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f;
const double FINF = 10000000;
const long long MOD = 1000000007;
const double PI = acos(-1);
struct {
  int lc, rc, sum;
} st[MAXN * 40];
int rt[MAXN], a[MAXN], b[MAXN], n, m, x, y, k, cnt, last = 0, Next[MAXN],
                                                    tmp[MAXN], lt[MAXN];
void update(int l, int r, int &x, int y, int pos) {
  st[++cnt] = st[y], st[cnt].sum++, x = cnt;
  if (l == r) return;
  int mid = (l + r) / 2;
  if (pos <= mid)
    update(l, mid, st[x].lc, st[y].lc, pos);
  else
    update(mid + 1, r, st[x].rc, st[y].rc, pos);
}
int query(int l, int r, int x, int pos) {
  if (pos <= l && r <= INF) return st[x].sum;
  int mid = (l + r) >> 1;
  if (pos <= mid)
    return query(l, mid, st[x].lc, pos) + st[st[x].rc].sum;
  else
    return query(mid + 1, r, st[x].rc, pos);
}
void dfs(int fa, int u, int cur) {
  if (cur == 0 || u == -1) {
    b[fa] = u;
    return;
  } else {
    dfs(fa, Next[u], cur - 1);
  }
}
int main() {
  scanf("%d%d", &n, &m);
  memset(tmp, -1, sizeof(tmp));
  memset(lt, -1, sizeof(lt));
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = n; i >= 1; --i) Next[i] = tmp[a[i]], tmp[a[i]] = i;
  for (int i = 1; i <= n; ++i) {
    if (lt[a[i]] == -1) {
      dfs(i, i, m);
    } else
      dfs(i, b[lt[a[i]]], 1);
    lt[a[i]] = i;
  }
  for (int i = 1; i <= n; ++i)
    if (b[i] == -1) b[i] = n + 1;
  for (int i = 1; i <= n; ++i) update(1, n + 1, rt[i], rt[i - 1], b[i]);
  int q;
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d", &x, &y);
    x = (x + last) % n + 1;
    y = (y + last) % n + 1;
    if (x > y) swap(x, y);
    last = query(1, n + 1, rt[y], y + 1) - query(1, n + 1, rt[x - 1], y + 1);
    printf("%d\n", last);
  }
}
