package main

import (
	"io"
	"os"
	"strconv"
)

func nextInt(data []byte, idx *int) int {
	n := len(data)
	for *idx < n {
		c := data[*idx]
		if c >= '0' && c <= '9' {
			break
		}
		*idx = *idx + 1
	}
	val := 0
	for *idx < n {
		c := data[*idx]
		if c < '0' || c > '9' {
			break
		}
		val = val*10 + int(c-'0')
		*idx = *idx + 1
	}
	return val
}

func lowerBound(arr []int, x int) int {
	l, r := 0, len(arr)
	for l < r {
		m := int(uint(l+r) >> 1)
		if arr[m] < x {
			l = m + 1
		} else {
			r = m
		}
	}
	return l
}

func merge(a, b []int) []int {
	if len(a) == 0 {
		return b
	}
	if len(b) == 0 {
		return a
	}
	c := make([]int, len(a)+len(b))
	i, j, k := 0, 0, 0
	for i < len(a) && j < len(b) {
		if a[i] <= b[j] {
			c[k] = a[i]
			i++
		} else {
			c[k] = b[j]
			j++
		}
		k++
	}
	for i < len(a) {
		c[k] = a[i]
		i++
		k++
	}
	for j < len(b) {
		c[k] = b[j]
		j++
		k++
	}
	return c
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	idx := 0

	n := nextInt(data, &idx)
	k := nextInt(data, &idx)

	occ := make([][]int, 100001)
	prevK := make([]int, n+1)

	for i := 1; i <= n; i++ {
		v := nextInt(data, &idx)
		lst := occ[v]
		if len(lst) >= k {
			prevK[i] = lst[len(lst)-k]
		}
		occ[v] = append(lst, i)
	}

	size := 1
	for size < n {
		size <<= 1
	}

	tree := make([][]int, size<<1)
	for i := 0; i < n; i++ {
		tree[size+i] = []int{prevK[i+1]}
	}
	for i := size - 1; i >= 1; i-- {
		tree[i] = merge(tree[i<<1], tree[i<<1|1])
	}

	q := nextInt(data, &idx)
	out := make([]byte, 0, q*8)
	last := 0

	for i := 0; i < q; i++ {
		x := nextInt(data, &idx)
		y := nextInt(data, &idx)

		l := (x + last) % n
		r := (y + last) % n
		l++
		r++
		if l > r {
			l, r = r, l
		}

		cnt := 0
		L := l + size - 1
		R := r + size - 1
		for L <= R {
			if (L & 1) == 1 {
				arr := tree[L]
				cnt += len(arr) - lowerBound(arr, l)
				L++
			}
			if (R & 1) == 0 {
				arr := tree[R]
				cnt += len(arr) - lowerBound(arr, l)
				R--
			}
			L >>= 1
			R >>= 1
		}

		ans := (r - l + 1) - cnt
		out = strconv.AppendInt(out, int64(ans), 10)
		out = append(out, '\n')
		last = ans
	}

	os.Stdout.Write(out)
}