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; ith 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. ith 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₁, a₂, ... a_n (1 ≤ a_i ≤ 100000).

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

Then q lines follow. ith line contains two numbers x_i and y_i which represent ith 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 ith plan, you have to do the following:

l_i = ((x_i + last) mod n) + 1;
r_i = ((y_i + last) mod n) + 1;
If l_i > r_i, swap l_i and r_i.

Output

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

Note

In the first example the real plans are:

1 2
1 6
6 6
2 4
4 6

Army Creation

Examples