Bajtocja 計劃再次進攻 Bitocja！對敵方領土進行空降作戰是真正硬漢的任務，因此 Bajtocja 最精銳的特種部隊——Bajtogrom 將參與其中。

在 Bajtczak 將軍的簡報會上，聚集了 $n$ 名士兵。由於他們經過多年的操練，能迅速排成一列，因此可以從左到右將他們編號為 $1$ 到 $n$ 的整數。將軍想要挑選若干個部隊，將他們空投到 Bitocja 的領土上。

作為一名熟練的戰略家，他知道部下排成這個順序並非沒有原因，而是因為他們之間有著友好的關係。因此，他所挑選的每個部隊都必須由恰好 $k$ 名佔據隊列中連續位置的士兵組成。這樣他就能確保組成部隊的士兵們會合作良好。當然，每名士兵最多只能屬於一個部隊，但將軍對於部隊的數量沒有任何偏好——特別是，他也可以選擇不挑選任何部隊，暫時放棄對 Bitocja 的進攻。

Bajtczak 將軍了解他士兵的能力——他可以用一個整數 $a_i$ 來描述每一名士兵。這個數值越高，該士兵在戰鬥中就越強。這個數值也可能是負數，這意味著該士兵可能只會阻礙行動。

將軍想要最大化所有被派去空降的士兵的 $a_i$ 值總和。然而，有一個陷阱。可能會發生這樣的情況：他必須將隊列中開頭的若干名士兵派往與 Intocja 的前線，並將隊列末尾的若干名士兵派往 Longlongtocja 執行情報任務。在這種情況下，他只能在位置編號包含在區間 $[l_i, r_i]$ 內的士兵中挑選部隊。

請幫助將軍考慮各種不同的情境，並為每個情境計算出被派去空降的士兵的 $a_i$ 值總和的最大可能值。

輸入格式

輸入的第一行包含三個整數 $n, k, q$ ($1 \le n, q \le 3 \cdot 10^5$; $1 \le k \le n$)，分別表示隊列中的士兵人數、每個部隊的士兵人數以及將軍考慮的情境數量。

第二行包含 $n$ 個整數 $a_1, \dots, a_n$ ($-10^9 \le a_i \le 10^9$)，如題目所述。

接下來的 $q$ 行，每行包含兩個整數。第 $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

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

說明

範例說明：在第一個和第五個情境中，Bajtczak 將軍應該派遣兩個部隊，分別由佔據位置 $[1, 2, 3]$ 和 $[5, 6, 7]$ 的士兵組成。

在第二個和第六個情境中，最優解是僅創建一個由佔據位置 $[3, 4, 5]$ 的士兵組成的部隊。

在第三個和第四個情境中，將軍不應該創建任何部隊，並冷靜地重新思考整個進攻計劃。

在第七個情境中，將軍應該創建兩個部隊，分別由佔據位置 $[1, 2, 3]$ 和 $[4, 5, 6]$ 的士兵組成。

子任務

在某些測試組中，$k \le 30$。