あなたは投資会社のトレーダーです。ある日、取引を担当している株の価格が、毎日まったく同じパターンを繰り返すことに気づきました。1 日は長さの等しい $n$ 個の時間帯に分けられ、第 $i$ 時間帯の株価は常に $a_i$ です。ある日の第 $n$ 時間帯が終わると、すぐに翌日の最初の時間帯が始まり、価格は $a_n$ から $a_1$ に変わります。これは一生に一度のチャンスです。すでに見抜いたこのパターンに従って勤務時間内に売買するだけで、確実に利益を得る方法があるのです！

あなたの勤務時間は一定ではなく、勤務期間が午前 0 時をまたぐこともあります。$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$ 回の取引を完了できます。1 回の取引は、株を 1 株買い、それより後の時間帯に売ることからなり、その利益は売却価格から購入価格を引いた値です。同時に保有できるのは最大 1 株なので、別の株を買う前に現在保有している株を売らなければなりません。すべての購入と売却は、その勤務期間内に、上記の時系列順に従って行わなければなりません。取引を一度も行わず、利益を $0$ とすることもできます。

各勤務期間について独立に、得られる合計利益の最大値を求めてください。

入力

1 行目には 3 つの整数 $n,k,q$（$1 \le n \le 10^5$、$1 \le k \le 800$、$1 \le q \le 3\times10^5$）が与えられます。これらは、それぞれ 1 日の時間帯の数、各勤務期間の最大取引回数、勤務期間の数です。

2 行目には $n$ 個の整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 10^6$）が与えられます。$a_i$ は毎日の第 $i$ 時間帯の株価です。

続く $q$ 行の各行には 2 つの整数 $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,\lfloor0.15n\rfloor),\max(1,\lfloor0.85n\rfloor)]$ から、独立に一様ランダムに生成されます。$r_i$ の値は $l_i$ と $\mathrm{len}_i$ によって一意に定まります。 特に、区間が $[1,1]$ の場合、ランダムに選ばれる値は常に $1$ です。

入出力例を除き、テストケースはちょうど 50 個あります。

出力

$q$ 行出力してください。第 $i$ 行には、第 $i$ 勤務期間に最大 $k$ 回の取引で得られる利益の最大値を表す整数を 1 つ出力してください。

入出力例

入力 1

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

出力 1

7
4
0