markdown

E. 军队组建

还记得我们之前的比赛吗？Vova 非常喜欢电脑游戏。现在他正在玩一款名为《帝国时代》的策略游戏。

在游戏中，Vova 可以雇佣 $n$ 个不同的战士；第 $i$ 个战士的类型为 $a_i$。Vova 想要通过雇佣一部分战士来组建一支平衡的军队。一支军队被称为平衡的，当且仅当对于游戏中出现的每一种类型的战士，该类型在军队中的数量不超过 $k$ 个。当然，Vova 希望他的军队尽可能庞大。

为了让事情更复杂，Vova 需要考虑 $q$ 个不同的军队组建方案。第 $i$ 个方案只允许他雇佣编号在 $l_i$ 到 $r_i$ 之间（包含两端）的战士。

请帮助 Vova 确定每个方案下平衡军队的最大可能规模。

注意，这些方案是以一种修改后的方式给出的。详见输入部分。

输入

• 第一行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 100000$）。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 100000$）。
• 第三行包含一个整数 $q$（$1 \le q \le 100000$）。
• 接下来 $q$ 行，第 $i$ 行包含两个数 $x_i$ 和 $y_i$，代表第 $i$ 个方案（$1 \le x_i, y_i \le n$）。

你需要记录上一个方案的答案（记为 $last$）。初始时 $last = 0$。为了还原第 $i$ 个方案的 $l_i$ 和 $r_i$，你需要执行以下操作：

• $l_i = ((x_i + last) \bmod n) + 1$；
• $r_i = ((y_i + last) \bmod n) + 1$；
• 如果 $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$ $2$
• $1$ $6$
• $6$ $6$
• $2$ $4$
• $4$ $6$