Army Creation

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem

Warrior $i$ has type $a_i$. From a decoded interval $[l,r]$, choose as many warriors as possible while taking at most $k$ of each type. Decode l=((x+last)mod n)+1 and r=((y+last)mod n)+1, then swap if needed.

Input

The first line contains $n,k$, the second line the types, the third line $q$, followed by $q$ encoded pairs $x,y$.

Output

Print each maximum army size and use it as last for the next query.

Subtasks

Subtask 1 (20%)

• $n\le 30$, number of queries $\le 30$.
• All other conditions are the same as Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, number of queries $\le 3000$.
• All other conditions are the same as Subtask 3.

Subtask 3 (50%)

• $1\le n,k\le10^5$
• $1\le a_i\le10^5$
• $1\le q\le10^5$
• $1\le x,y\le n$

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

Explanation

With $k=2$, at most two warriors of every type can be chosen. Intervals are decoded sequentially using the previous answer.