CF813E.Army Creation

As you might remember from our previous rounds, Vova really likes computer games. Now he is playing a strategy game known as Rage of Empires.

In the game Vova can hire n different warriors; _i_th warrior has the type a__i. Vova wants to create a balanced army hiring some subset of warriors. An army is called balanced if for each type of warrior present in the game there are not more than k warriors of this type in the army. Of course, Vova wants his army to be as large as possible.

To make things more complicated, Vova has to consider q different plans of creating his army. _i_th plan allows him to hire only warriors whose numbers are not less than l__i and not greater than r__i.

Help Vova to determine the largest size of a balanced army for each plan.

Be aware that the plans are given in a modified way. See input section for details.

正如我们在之前的轮次中所记得的那样，Vova 非常喜欢电脑游戏。现在他正在玩一款名为《帝国狂怒》（Rage of Empires）的策略游戏。

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

为了使问题更复杂，Vova 还需考虑 $q$ 种不同的建军方案。其中第 $i$ 个方案只允许他雇佣编号不小于 $l_i$ 且不大于 $r_i$ 的战士。

请帮助 Vova 确定每种方案下所能组成的最大规模的平衡军队。

注意：这些方案是以一种修改后的方式给出的。具体细节请参见输入格式部分。

The first line contains two integers n and k (1 ≤ n, k ≤ 100000).

The second line contains n integers _a_1, _a_2, ... a__n (1 ≤ a__i ≤ 100000).

The third line contains one integer q (1 ≤ q ≤ 100000).

Then q lines follow. _i_th line contains two numbers x__i and y__i which represent _i_th plan (1 ≤ x__i, y__i ≤ n).

You have to keep track of the answer to the last plan (let's call it last). In the beginning last = 0. Then to restore values of l__i and r__i for the _i_th plan, you have to do the following:

1. l__i = ((x__i + last) mod n) + 1;
2. r__i = ((y__i + last) mod n) + 1;
3. If l__i > r__i, swap l__i and r__i.

第一行包含两个整数 $n$ 和 $k$（$1 \leq n, k \leq 100000$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$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) \bmod n) + 1$；
2. $r_i = ((y_i + last) \bmod n) + 1$；
3. 若 $l_i > r_i$，则交换 $l_i$ 和 $r_i$。

Print q numbers. _i_th number must be equal to the maximum size of a balanced army when considering _i_th plan.

输出 $q$ 个数。其中第 $i$ 个数必须等于在考虑第 $i$ 个方案时，所能组成的平衡军队的最大规模。

In the first example the real plans are:

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

在第一个例子中，实际的计划是：

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