E. Army Creation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 1, a 2, ... 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:

  1. l i = ((x i + lastmod n) + 1;
  2. r i = ((y i + lastmod n) + 1;
  3. 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.

Example
Input
6 2
1 1 1 2 2 2
5
1 6
4 3
1 1
2 6
2 6
Output
2
4
1
3
2
Note

In the first example the real plans are:

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