题目描述

在游戏中，小达可以雇佣 $n$ 个不同的战士，第 $i$ 个战士的类型是 $a_i$。小达想要从这些战士里挑选一些战士组成一个平衡型军队——如果游戏中每种类型的战士在军队中都不超过 $k$ 个，那么这只军队就被成为平衡型军队。当然，小达希望自己的军队越大越好。

让事情变得更复杂的是，小达必须考虑 $q$ 个不同的组建军队的计划。第 $i$ 个计划只允许他雇佣人数不少于 $l_i$ 也不多于 $r_i$ 的战士。

请你帮助小达确定每个计划的平衡型军队的最大规模。

请注意，计划是以修改过的方式给出的。详情请参见输入部分。

输入格式

第一行，两个整数 $n$ 和 $k$，$1 \leq n,k, \leq 100000$。

第二行，$n$ 个整数 $a_i~(1 \leq a_i \leq 100000)$。

第三行，一个整数 $q~(1 \leq q \leq 100000)$。

接下来是 $q$ 行。第 $i$ 行包含两个数字 $x_i$ 和 $y_i$，他们代表第 $i$ 次计划（$1 \leq x_i,~y_i \leq n$）。

你必须记住上一个计划的答案（我们称之为 $last$）。最开始 $last = 0$。然后，为了恢复第 $i$ 次计划的 $l_i$ 和 $r_i$ 值，我们必须执行以下操作：

1. $l_i = ((x_i + last) \mod n) + 1$;
2. $r_i = ((y_i + last) \mod n) + 1$;
3. 如果是 $l_i > r_i$，交换 $l_i$ 和 $r_i$。

输出格式

打印 $q$ 个数字。在考虑第 $i$ 个计划时，第 $i$ 个数字必须等于平衡型军队的最大规模。

样例

6 2
1 1 1 2 2 2
5
1 6
4 3
1 1
2 6
2 6

2
4
1
3
2

提示

样例 1 解释

真正的计划是：

1. 1 2
2. 1 6
3. 6 6
4. 2 4
5. 4 6

数据范围

对于 $30 \%$ 的数据满足 $1 \leq n,k,a_i,q \leq 100$。

对于 $100 \%$ 的数据满足 $1 \leq n,k,a_i,q \leq {10}^5$。