你可能还记得我们前几轮的内容,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