Maximizing Deployment Efficiency

General Bytchak has gathered \( n \) soldiers, numbered from 1 to \( n \) from left to right. He wants to deploy some of his best soldiers in a special operation by forming teams. Each team must consist of exactly \( k \) consecutive soldiers. Note that each soldier can belong to at most one team, and the general may choose not to form any team.

Each soldier has a skill value \( a_i \) (which may be negative), representing his battlefield efficiency. The general's aim is to maximize the sum of the skill values of all soldiers who are deployed (i.e. those who are chosen as part of some team).

However, due to strategic reasons, the general sometimes must only choose teams from a specific segment of the lineup. For a given query with boundaries \( l \) and \( r \), you are only allowed to consider soldiers whose positions lie in the interval \( [l, r] \). That is, any team formed must lie completely within \( [l, r] \).

Your task is to help the general calculate the maximum possible sum of skill values for the deployed soldiers for each given query.

inputFormat

The first line contains three integers \( n \), \( k \), and \( q \) — the number of soldiers, the fixed team size, and the number of queries, respectively.

The second line contains \( n \) integers \( a_1, a_2, \ldots, a_n \) representing the skill values of the soldiers.

Each of the next \( q \) lines contains two integers \( l \) and \( r \), representing a query where you are only allowed to choose teams completely within the segment \( [l, r] \).

outputFormat

For each query, output a single integer representing the maximum possible sum of the skill values of the deployed soldiers. If no valid team can be formed, output 0.

sample

5 2 3
1 2 3 4 5
1 5
2 4
3 3

14
7
0