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.**
## Input
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_.
## Output
Print _q_ numbers. _i_th number must be equal to the maximum size of a _balanced_ army when considering _i_th plan.
[samples]
## Note
In the first example the real plans are:
1. 1 2
2. 1 6
3. 6 6
4. 2 4
5. 4 6
正如你在我们之前的比赛中所记得的，Vova 非常喜欢电子游戏。现在他正在玩一款名为《帝国怒火》的战略游戏。
在游戏中，Vova 可以雇佣 #cf_span[n] 名不同的战士；第 #cf_span[i] 名战士的类型为 #cf_span[ai]。Vova 希望通过选择一部分战士来组建一支 _平衡_ 的军队。一支军队被称为 _平衡_ 的，是指对于游戏中存在的每种战士类型，军队中该类型的战士数量不超过 #cf_span[k]。当然，Vova 希望他的军队尽可能大。
为了使事情更加复杂，Vova 必须考虑 #cf_span[q] 种不同的组建军队方案。第 #cf_span[i] 种方案只允许他雇佣编号不小于 #cf_span[li] 且不大于 #cf_span[ri] 的战士。
请帮助 Vova 确定每种方案下 _平衡_ 军队的最大规模。
*请注意，这些方案是以修改后的形式给出的。详情请参见输入部分。*
第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n, k ≤ 100000])。
第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ... #cf_span[an] (#cf_span[1 ≤ ai ≤ 100000])。
第三行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 100000])。
接下来 #cf_span[q] 行，每行包含两个数字 #cf_span[xi] 和 #cf_span[yi]，表示第 #cf_span[i] 种方案 (#cf_span[1 ≤ xi, yi ≤ n])。
你必须记录上一个方案的答案（记作 #cf_span[last]）。初始时 #cf_span[last = 0]。为了恢复第 #cf_span[i] 种方案的 #cf_span[li] 和 #cf_span[ri] 值，你需要执行以下操作：
请输出 #cf_span[q] 个数字。第 #cf_span[i] 个数字必须等于考虑第 #cf_span[i] 种方案时 _平衡_ 军队的最大规模。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[1 ≤ n, k ≤ 100000])。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ... #cf_span[an] (#cf_span[1 ≤ ai ≤ 100000])。第三行包含一个整数 #cf_span[q] (#cf_span[1 ≤ q ≤ 100000])。接下来 #cf_span[q] 行，每行包含两个数字 #cf_span[xi] 和 #cf_span[yi]，表示第 #cf_span[i] 种方案 (#cf_span[1 ≤ xi, yi ≤ n])。你必须记录上一个方案的答案（记作 #cf_span[last]）。初始时 #cf_span[last = 0]。为了恢复第 #cf_span[i] 种方案的 #cf_span[li] 和 #cf_span[ri] 值，你需要执行以下操作：
#cf_span[li = ((xi + last) mod n) + 1];
#cf_span[ri = ((yi + last) mod n) + 1];
如果 #cf_span[li > ri]，则交换 #cf_span[li] 和 #cf_span[ri]。
## Output
请输出 #cf_span[q] 个数字。第 #cf_span[i] 个数字必须等于考虑第 #cf_span[i] 种方案时 _平衡_ 军队的最大规模。
[samples]
## Note
在第一个例子中，真实的方案是：
#cf_span[1 2]
#cf_span[1 6]
#cf_span[6 6]
#cf_span[2 4]
#cf_span[4 6]
**Definitions**
Let $ n, k \in \mathbb{Z}^+ $, $ A = (a_1, a_2, \dots, a_n) $ with $ a_i \in \mathbb{Z}^+ $, $ q \in \mathbb{Z}^+ $.
Let $ \text{last} = 0 $ initially. For each plan $ i \in \{1, \dots, q\} $, given $ (x_i, y_i) $, compute:
$$
l_i = ((x_i + \text{last}) \bmod n) + 1, \quad r_i = ((y_i + \text{last}) \bmod n) + 1
$$
Then let $ L_i = \min(l_i, r_i) $, $ R_i = \max(l_i, r_i) $.
**Constraints**
1. $ 1 \le n, k \le 100000 $
2. $ 1 \le a_i \le 100000 $
3. $ 1 \le q \le 100000 $
4. $ 1 \le x_i, y_i \le n $
**Objective**
For each plan $ i \in \{1, \dots, q\} $, compute the maximum size of a balanced army over the subarray $ A[L_i:R_i] $, where a balanced army satisfies:
- For each warrior type $ t $, the count of warriors of type $ t $ in the army is at most $ k $.
- The army is a subset of warriors in positions $ \{L_i, L_i+1, \dots, R_i\} $.
That is, for each plan $ i $, compute:
$$
\max \left\{ \sum_{t} \min(c_t, k) \,\middle|\, c_t = \left| \{ j \in [L_i, R_i] : a_j = t \} \right| \right\}
$$