Migrated from Lutece 3032 Overkill for AK Prevention

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

For a sequence $s_1,s_2,\ldots,s_t$ of length $t$, each time you can choose a subinterval $[l,r]$ $(1\le l\le r\le t)$, and subtract $1$ from each number ($a_l,a_{l+1},\ldots,a_r$) in this subinterval (note that it is not allowed to reduce any number to a negative number). At least how many operations are required to reduce all numbers in the sequence to $0$? - This is a classic problem solved by difference.

Now let's upgrade: we stipulate that the length of the interval selected each time cannot exceed $m$, that is, $r-l+1\le m$.

Now let's upgrade it again: given a sequence $a_1,a_2,\ldots,a_n$ of length $n$, you need to answer $q$ queries, and each query is of the form $[L,R]$ $( 1\le L\le R\le n)$, meaning that you need to calculate the answer to the above question for the subsequence $a_L,a_{L+1},\ldots,a_{R}$.

Can you do it?

Input

The first line contains three integers $n, m, q$ $(1\le m\le n\le 10^5,1\le q\le 10^5)$, respectively representing the length of the sequence $a$, The maximum length of the interval allowed for each operation, and the number of inquiries;

The second line contains $n$ integers representing the sequence $a_1,a_2,\ldots,a_n$ $(0\le a_i\le 10^9)$;

Then $q$ line follows, where the $(2+i)$-th line contains two integers $L_i,R_i$ $(1\le L_i\le R_i\le n)$, denoting the queried subinterval.

Output

A total of $q$ rows, where the $i$-th row contains an integer representing the answer to the $i$-th query.

Samples

4 3 1
1 2 1 1
1 4

2

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

6
9
10