You have arranged balloons in a linear order. Every balloon is colored and the $i^{th}$ balloon's color is represented by $C_i$. Here, the color of balloons is depicted with numbers. 

The number $k$ is not a suitable number, therefore you decide to use it for the less number of times. You do not contain any range of ballons in which a color repeats exactly $k$ times. If the displayed balloons are numbered from $b_0,b_1,b_2,...,b_{n-1}$, then the range of balloons from $l$ to $r$ is $b_l,b_{l+1},b_{l+2},...,b_r$.

You are provided with some specific ranges and your task is to determine the number of colors that get repeated for exactly $k$ times in each range that is provided.

Input format

• First line: Three integers $n$, $k$, and $q$ ($1\le n,k,q\le 100000$). Here, $n$ is the number of balloons, $k$ is the inappropriate number, and $q$ is the number of queries.
• Second line: Contains $n$ integers depicting the color of balloons ($1\le ci\le 1000\cdot 1000\cdot 1000$)
• Each $q$ lines: Contains two integers $l$ and $r$ (\(0\le l,\ r)

Output format

Print the number of colors that are repeated exactly k times. If the answer to the previous query is $ans$ (answer for the first query is $0$), then the range of the answer should be $min((l+ans)\mathrm{\%}n,(r+ans)\mathrm{\%}n)andmax((l+ans)\mathrm{\%}n,(r+ans)\mathrm{\%}n)$.

.