1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
using ll = long long;
constexpr int tree_size = (1 << 19);
constexpr int MAXK = 32, MAXN=3e5+10;
int r = 1, n, k, q;
// ll tree[2*tree_size][2][MAXK];

ll pref[MAXN];
ll dp[MAXN];

// void build_tree(int st, int en, int v=1)
// {
//     if (en - st + 1 < k) {
//         return;
//     }

//     if (st == en) {
//         tree[v][0][0] = tree[v][1][0] = max(0LL, pref[st] - pref[st-1]);
//         return;
//     }

//     build_tree(st, (st+en)/2, 2*v);
//     build_tree((st+en)/2+1, en, 2*v+1);

//     for(int i=; i >=0; i--)
//     {

//     }
// }

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n >> k >> q;

    for (int i=1; i <= n; i++)
    {
        int x;
        cin >> x;
        pref[i] = pref[i-1] + x;
    }  

    // while(r <= n)
    // {
    //     r *= 2;
    // }

    for (int i=0; i < q; i++)
    {
        int a, b;
        cin >> a >> b;

        for (int j=a-1; j <= min(a + k, b); j++)
        {
            dp[j] = 0;
        }

        for (int j=a + k - 1; j <= b; j++)
        {
            dp[j] = max(dp[j-1], dp[j-k] + pref[j] - pref[j-k]);
        }

        cout << dp[b] << "\n";

    }
    
}