Bajtocjaは再びBitocjaを攻撃しようと計画しています！敵地への降下作戦は真の強者たちの任務であり、そのためBajtocjaの精鋭特殊部隊であるBajtogromの兵士たちが参加することになりました。

Bajtczak将軍のブリーフィングには $n$ 人の兵士が集まりました。彼らは長年の訓練のおかげで、瞬時に一列に整列し、左から右へ $1$ から $n$ までの整数で番号を振ることができました。将軍は、Bitocjaの領土に投入するいくつかの部隊を選びたいと考えています。

熟練した戦略家である将軍は、部下たちが現在の順序で並んでいるのには理由があり、彼らの間の友好関係に基づいていることを知っています。そのため、将軍が選ぶ各部隊は、列の中で連続した位置を占めるちょうど $k$ 人の兵士で構成されていなければなりません。これにより、部隊としてまとめられた兵士たちがうまく協力できることを確信できます。もちろん、各兵士は最大で1つの部隊にしか所属できませんが、将軍は部隊の数については何のこだわりもありません。特に、部隊を1つも選ばず、攻撃を中止することも可能です（少なくとも現時点では）。

Bajtczak将軍は兵士たちの能力を知っており、各兵士を整数 $a_i$ で表すことができます。この値が大きいほど、その兵士は戦闘において有能です。この値は負になることもあり、その場合はその兵士が作戦の妨げになる可能性が高いことを意味します。

将軍は、降下作戦に送られるすべての兵士の $a_i$ の合計を最大化したいと考えています。しかし、一つ問題があります。列の先頭にいる何人かの兵士をIntocjaとの前線に送らなければならず、列の末尾にいる何人かの兵士をLonglongtocjaでの諜報活動に送らなければならない可能性があります。その場合、将軍は位置番号が $[l_i, r_i]$ の範囲に含まれる兵士の中からのみ部隊を選ぶ必要があります。

将軍がさまざまなシナリオを検討するのを手伝い、それぞれのシナリオについて、降下作戦に送られる兵士の $a_i$ の合計の最大値を計算してください。

入力

入力の最初の行には、3つの整数 $n, k, q$ ($1 \le n, q \le 3 \cdot 10^5$; $1 \le k \le n$) が含まれており、それぞれ列に並んだ兵士の数、各部隊の兵士の数、将軍が検討するシナリオの数を表します。

2行目には、問題文で説明されている $n$ 個の整数 $a_1, \dots, a_n$ ($-10^9 \le a_i \le 10^9$) が含まれています。

続く $q$ 行には、それぞれ2つの整数が含まれています。$i$ 番目の行には $l_i$ と $r_i$ ($1 \le l_i \le r_i \le n$) が含まれています。これらは、$i$ 番目のシナリオでは、位置番号が $[l_i, r_i]$ の範囲内にある兵士のみを降下作戦に送ることができることを意味します。

出力

出力は $q$ 行からなる必要があります。$i$ 番目の行には、$i$ 番目のシナリオにおいてBitocjaに送られる兵士の $a_i$ の合計の最大値を表す整数を1つ出力してください。

入出力例

入力 1

8 3 7
3 -1 10 0 10 -1 1 -1
1 8
3 5
6 8
1 2
1 7
2 8
1 6

出力 1

22
20
0
0
22
20
21

注記

例の解説：第1および第5のシナリオでは、Bajtczak将軍は位置 $[1, 2, 3]$ および $[5, 6, 7]$ を占める兵士で構成される2つの部隊を降下作戦に送るべきです。

第2および第6のシナリオでは、位置 $[3, 4, 5]$ を占める兵士で構成される1つの部隊のみを作成するのが最適です。

第3および第4のシナリオでは、将軍は部隊を1つも作成せず、攻撃計画全体を冷静に考え直すべきです。

第7のシナリオでは、将軍は位置 $[1, 2, 3]$ および $[4, 5, 6]$ を占める兵士で構成される2つの部隊を作成すべきです。

小課題

一部のテストグループでは、$k \le 30$ が成り立ちます。