당신은 투자 회사의 트레이더이다. 어느 날, 당신은 자신이 거래를 담당하는 주식이 매일 정확히 반복되는 패턴을 따른다는 사실을 발견한다. 하루는 길이가 같은 $n$개의 시간 구간으로 나뉘며, $i$번째 구간 동안의 주가는 항상 $a_i$이다. 어느 날의 $n$번째 구간이 끝나면 다음 날의 첫 번째 구간이 즉시 이어지고, 주가는 $a_n$에서 $a_1$로 바뀐다. 이는 일생에 한 번 있을 기회이다. 이미 알아낸 이 패턴에 맞춰 근무 시간 동안 주식을 사고팔기만 하면, 확실하게 이익을 얻을 수 있다!

당신의 근무 시간은 일정하지 않으며, 한 근무 기간이 자정을 넘길 수도 있다. $q$개의 근무 기간이 주어진다. $i$번째 기간은 시간 구간 $l_i$에서 시작하여 시간 구간 $r_i$에서 끝나며, 양 끝 구간을 모두 포함한다. 시간 순서대로 나열한 구간은 다음과 같다.

• $l_i \le r_i$이면 $l_i,l_i+1,\ldots,r_i$이다.
• $l_i > r_i$이면 $l_i,l_i+1,\ldots,n,1,2,\ldots,r_i$이다.

각 근무 기간 동안 최대 $k$번의 거래를 완료할 수 있다. 한 번의 거래는 주식 한 주를 매수한 뒤 나중의 시간 구간에 매도하는 것으로 이루어지며, 이익은 매도 가격에서 매수 가격을 뺀 값이다. 동시에 최대 한 주만 보유할 수 있으므로, 다른 주식을 매수하기 전에 현재 보유한 주식을 매도해야 한다. 모든 매수와 매도는 해당 근무 기간 안에서 이루어져야 하며, 위에서 설명한 시간 순서를 따라야 한다. 거래를 전혀 하지 않아 $0$의 이익을 얻을 수도 있다.

각 근무 기간에 대해 독립적으로, 얻을 수 있는 총이익의 최댓값을 구하여라.

입력

첫째 줄에는 세 정수 $n,k,q$ ($1 \le n \le 10^5$, $1 \le k \le 800$, $1 \le q \le 3 \times 10^5$)가 주어진다. 각각 하루의 시간 구간 수, 근무 기간마다 허용되는 최대 거래 횟수, 근무 기간 수이다.

둘째 줄에는 $n$개의 정수 $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^6$)이 주어진다. $a_i$는 매일 $i$번째 시간 구간의 주가이다.

다음 $q$개 줄에는 각각 두 정수 $l_i,r_i$ ($1 \le l_i,r_i \le n$)가 주어지며, $i$번째 근무 기간을 나타낸다.

이 기간의 시간 구간 수를 $\mathrm{len}_i$라고 하자. $l_i \le r_i$이면 $\mathrm{len}_i=r_i-l_i+1$이고, 그렇지 않으면 $\mathrm{len}_i=n-l_i+1+r_i$이다.

각 근무 기간에 대해 $l_i$와 $\mathrm{len}_i$는 각각 $[1,n]$과 $[\max(1,\lfloor 0.15n \rfloor),\max(1,\lfloor 0.85n \rfloor)]$에서 서로 독립적으로 균등한 확률로 무작위로 생성된다. $r_i$의 값은 $l_i$와 $\mathrm{len}_i$에 의해 유일하게 결정된다. 구체적으로, 구간이 $[1,1]$이면 무작위 생성 결과는 항상 $1$이다.

예제를 제외하고 테스트 케이스는 정확히 50개이다.

출력

$q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 근무 기간 동안 최대 $k$번의 거래로 얻을 수 있는 최대 이익을 나타내는 정수 하나를 출력한다.

예제

입력 1

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

출력 1

7
4
0