Byteotia is planning to attack Bitotia again! A landing on enemy territory is a task for true tough guys, which is why soldiers from the best Byteotian special unit – the Byte-thunder – will take part in it.

At General Bajtczak's briefing, $n$ soldiers gathered. Thanks to many years of drill training, they instantly lined up, allowing them to be numbered from left to right with integers from $1$ to $n$. The General would like to select a certain number of squads to deploy to Bitotia's territory.

As a skilled strategist, he knows that his subordinates lined up in this order for a reason, specifically due to the friendly relations between them. Therefore, every squad he chooses must consist of exactly $k$ soldiers occupying a contiguous range of positions in the line. This ensures that the soldiers combined into squads will cooperate well. Of course, each soldier can belong to at most one squad, but the General has no preferences regarding the number of squads – in particular, he may choose not to select any and abandon the attack on Bitotia (at least for now).

General Bajtczak knows the skills of his soldiers – he can describe each of them with an integer $a_i$. The higher this value, the more efficient the soldier is in combat. This number can also be negative, which means the soldier will likely only hinder the operation.

The General would like to maximize the sum of the $a_i$ values of all soldiers sent on the landing. However, there is a catch. It may happen that he has to send a certain number of the first soldiers in the line to the front with Intotia, and a certain number of the last soldiers in the line on intelligence missions in Longlongtocia. In that case, he will have to choose squads only from among the soldiers whose position numbers are within the range $[l_i, r_i]$.

Help the General consider various scenarios and, for each of them, calculate the maximum possible sum of the $a_i$ values of the soldiers sent on the landing.

Input

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

The second line contains $n$ integers $a_1, \dots, a_n$ ($-10^9 \le a_i \le 10^9$) described in the problem statement.

The next $q$ lines each contain two integers. The $i$-th of these lines contains the numbers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$). They mean that in the $i$-th scenario, only soldiers with position numbers within the range $[l_i, r_i]$ can be sent on the landing.

Output

The output should contain $q$ lines. The $i$-th line should contain a single integer representing the maximum sum of the $a_i$ values of the soldiers sent to Bitotia in the $i$-th scenario.

Examples

Input 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

Output 1

22
20
0
0
22
20
21

Note

In the first and fifth scenarios, General Bajtczak should send two squads on the landing, consisting of soldiers occupying positions $[1, 2, 3]$ and $[5, 6, 7]$.

In the second and sixth scenarios, it is optimal to create only one squad consisting of soldiers occupying positions $[3, 4, 5]$.

In the third and fourth scenarios, the General should not create any squad and calmly rethink the entire attack plan.

In the seventh scenario, the General should create two squads, consisting of soldiers occupying positions $[1, 2, 3]$ and $[4, 5, 6]$.

Subtasks

In some test groups, $k \le 30$.