← 返回题目列表

Codeforces · 813/E

E. 军队创建

中文机器翻译题面 查看原题

你可能还记得我们前几轮的内容,Vova 非常喜欢电脑游戏。现在他正在玩一款名为《帝国之怒》的策略游戏。

游戏中Vova可以雇佣n个不同的战士;第 i 个战士的类型为 ai。沃瓦希望建立一支平衡的军队,雇佣一些战士。如果对于游戏中存在的每种类型的战士,军队中这种类型的战士不超过 k 个,则称军队是平衡的。当然,沃瓦希望他的军队尽可能庞大。

让事情变得更加复杂的是,Vova 必须考虑创建军队的不同计划。第i个计划允许他只雇佣数量不小于li且不大于ri的战士。

帮助 Vova 确定每个计划的平衡军队的最大规模。

请注意,计划是以修改的方式给出的。详细信息请参见输入部分。

输入

第一行包含两个整数 n 和 k (1 ≤ n, k ≤ 100000)。

第二行包含 n 个整数 a1, a2, ... an (1 ≤ ai ≤ 100000)。

第三行包含一个整数 q (1 ≤ q ≤ 100000)。

接下来是 q 行。第 i 行包含两个数字 xi 和 yi,它们代表第 i 个计划 (1 ≤ xi, yi ≤ n)。

你必须跟踪最后一个计划的答案(我们称其为最后一个)。一开始,last = 0。然后要恢复第 i 个计划的 li 和 ri 值,您必须执行以下操作:

1. li = ((xi + last) mod n) + 1;
2. ri = ((yi + last) mod n) + 1;
3. 如果 li > ri,则交换 li 和 ri。

输出

打印 q 个数字。在考虑第 i 个计划时,第 i 个数量必须等于均衡军队的最大规模。

示例

输入 #1

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

输出 #1

2
4
1
3
2

注意

在第一个示例中,真正的计划是:

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