Problem Description

Byteotia is preparing to attack Bitotia again. Landing on enemy territory is a job for real tough guys, so Byteotia’s best special forces soldiers—Byteburg—will take part in it.

General Bytchak gathers $n$ soldiers. They immediately line up in a row and are numbered with integers from $1$ to $n$ from left to right. The general wants to select some troops to redeploy into Bitotia. As a skilled strategist, he knows the order of his subordinates is not random, but related to the friendly relations between them, so each troop he selects must consist of exactly $k$ consecutive soldiers. In this way, he can ensure that the soldiers in a squad can cooperate well. Of course, each soldier can belong to at most one squad, and the general has no preference about the number of squads—in particular, he may choose no squads at all and give up the attack on Bitotia (at least for now).

General Bytchak knows the skill of each soldier—he can describe each of them by an integer $a_i$. The higher the skill value, the more effective the soldier is in battle. This value can also be negative, meaning that the soldier may only hinder the operation.

The general wants to maximize the sum of $a_i$ over all soldiers that will be sent to land. However, there is one issue. He may need to send some leading soldiers to the front line to fight Intotia, and send some trailing soldiers to carry out intelligence operations in Longlongotia. Then he will have to select troops only from soldiers whose positions are within the range $[l_i, r_i]$.

Please help the general consider different scenarios, and for each scenario compute the maximum possible sum of $a_i$ of the soldiers sent to land.

Input Format

The first line contains three integers $n, k, q$, representing the total number of soldiers, the number of soldiers in each squad, and the number of scenarios the general considers.

The second line contains $n$ integers $a_1, a_2, \cdots, a_n$, representing the skill value of each soldier.

The next $q$ lines follow. The $i$-th line contains two integers $l_i, r_i$, representing the $i$-th scenario, i.e. only soldiers with indices in the range $[l_i, r_i]$ can participate in the battle in Bitotia.

Output Format

Output $q$ lines. The $i$-th line contains one integer, representing the maximum sum of skill values of the soldiers participating in the battle in the $i$-th scenario.

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

22
20
0
0
22
20
21

Hint

For $100\%$ of the data, $1 \leq n, q \leq 3 \times 10^5$, $1 \leq k \leq n$, $-10^9 \leq a_i \leq 10^9$, $1 \leq l_i \leq r_i \leq n$.

Translated by ChatGPT 5