Desant 2

Bajtocja plans to attack Bitocja again. A landing behind enemy lines is a job for real tough guys, so soldiers of Bajtogrom, the best special unit of Bajtocja, will take part.

General Bajtczak has gathered $n$ soldiers at a briefing. They lined up in a row and are numbered from $1$ to $n$ from left to right. The general wants to choose some number of squads to send to Bitocja. Each squad must consist of exactly $k$ soldiers that occupy a contiguous range of positions. Each soldier belongs to at most one squad. The general has no preference for the number of squads, and he may choose none and call off the attack for now.

Each soldier is described by an integer $a_i$. The higher the value, the more effective the soldier is in combat. The value can also be negative, meaning that soldier will only get in the way.

The general wants to maximize the sum of $a_i$ over all soldiers sent on the landing. However, some of the first soldiers in the row must be sent to the front with Intocja, and some of the last soldiers must go on intelligence work in Longlongtocja. Therefore, squads may only be chosen from soldiers whose positions lie in the range $[l_i, r_i]$. For each scenario, compute the maximum possible sum of $a_i$ for the soldiers sent.

The first line contains three integers $n$, $k$, and $q$ ($1 \le n, q \le 3 \cdot 10^5$, $1 \le k \le n$), the number of soldiers, the number of soldiers in each squad, and the number of scenarios.

The second line contains $n$ integers $a_1, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$).

Each of the next $q$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$). In the $i$-th scenario, only soldiers whose positions lie in $[l_i, r_i]$ may be sent.

Print $q$ lines. The $i$-th line contains the maximum possible sum of $a_i$ for the soldiers sent to Bitocja in the $i$-th scenario.

In the first and fifth scenarios, the optimal choice is two squads, covering positions $[1, 2, 3]$ and $[5, 6, 7]$. In the second and sixth scenarios, the optimal choice is a single squad covering positions $[3, 4, 5]$. In the third and fourth scenarios, the general should not form any squad and instead think the plan over calmly. In the seventh scenario, the general should form two squads, covering positions $[1, 2, 3]$ and $[4, 5, 6]$.