#pragma GCC optimize("O3")

// #define DANE1
// #define DANE2
// #define DANE2

// #define DEBUG
// #define BEZ_RANDA

#include<bits/stdc++.h>
using namespace std;


const int GRANICA = 30000; //  wszystkie krótsze robię z łapy
const int STALA_DL = 800;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 rng(1);
#define losuj(a, b) uniform_int_distribution<long long>(a, b)(rng)

#define sz(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define f first
#define s second
#define pb push_back

#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>
#define vvi vector<vi>
#define vvii vector<vii>

#define ll long long

const int N = 3e5 + 7;

int tab[N];
ll pref[N];
int n, k, q;
ii queries[N];
ll pom[N];
ll DP[N];
ll ans[N];

void prep(){
    for(int i = 1; i <= n; i++){
        pref[i] = pref[i - 1] + tab[i];
        if(i >= k)
            pom[i] = pref[i] - pref[i - k];
    }
}
int used_as_przed[N];

void solve() {
#if not defined(DANE1) && not defined(DANE2) && not defined(DANE3)
    cin >> n >> k >> q;
    for(int i = 1; i <= n; i++)
        cin >> tab[i];

    for(int i = 0; i < q; i++)
        cin >> queries[i].f >> queries[i].s;
#endif

#ifdef DANE1
    n = 300 * 1000;
    k = 1000;
    q = 300 * 1000;

    for(int i = 0; i < q; i++){
        int pocz = losuj(1, n / 2);
        queries[i] = {pocz, pocz + 70000 + losuj(0, 1000)};
    } // na SIO2 robi się około 35 sekund pierwszą metodą
#endif

#ifdef DANE2
    n = 300 * 1000;
    k = 31;
    q = 300 * 1000;

    for(int i = 0; i < q; i++){
        int pocz = losuj(1, 5000);
        queries[i] = {pocz, pocz + n - 10000 + losuj(0, 1000)};
    }
#endif 

#ifdef DANE3
    n = 300 * 1000;
    k = 700;
    q = 300 * 1000;

    for(int i = 0; i < q; i++){
        int pocz = losuj(1, n / 2);
        queries[i] = {pocz, pocz + GRANICA - losuj(2, 10)};
    }
#endif 

    prep();
    ll dlugosci = 0;
    for(int i = 0; i < q; i++)
        dlugosci += (queries[i].s - queries[i].f + 1);

    if(dlugosci <= 1ll * 70000 * 300000){
        for(int query = 0; query < q; query++){
            int a = queries[query].f;
            int b = queries[query].s;
            ll maxi = 0;
            for(int i = a - 1; i <= min(a + k - 2, n); i++)
                DP[i] = 0;
            for(int i = a + k - 1; i <= b; i++){
                DP[i] = max(DP[i - 1], pom[i] + maxi);
                maxi = max(maxi, DP[i - k + 1]); 
            }
            cout << DP[b] << '\n';
        }
        return;
    }

    int CLOCK_LIMIT = 41.0;
    
#ifdef DEBUG
    if(n <= GRANICA)
        CLOCK_LIMIT = 0.0;
    cerr << "N: " << n << ", K: " << k << ", Q:" << q << endl;
#endif

#ifdef DEBUG
    int male = 0;
    int duze = 0;
#endif

    for(int query = 0; query < q; query++){ // robienie małych z łapy
        int a = queries[query].f;
        int b = queries[query].s;
        int dlugosc = b - a + 1;

        if(dlugosc <= GRANICA){

            #ifdef DEBUG
            male++;
            #endif

            for(int i = a - 1; i <= min(a + k - 2, b); i++)
                DP[i] = 0;
            for(int i = a + k - 1; i <= b; i++)
                DP[i] = max(DP[i - 1], pom[i] + DP[i - k]);
            ans[query] = DP[b];
        }
        else{

            #ifdef DEBUG
            duze++;
            #endif

            if(k <= 30)
                continue;

            int z_dlugosci = dlugosc / k;
            int niewziete = min(STALA_DL - z_dlugosci, k / 5); // chyba działa?

            if(niewziete < dlugosc % k) // nie da sie - czyli na pewno wcześniej wylosowało wcześniej
                continue; // w sensie wtedy ten for co jest za chwile nie ma sensu

            // robimy dp od a do b
            for(int i = a - 1; i <= min(b, a + niewziete); i++)
                DP[i] = 0;

            int pocz = a + k - 1;
            while(pocz <= b){
                DP[pocz] = DP[pocz - k] + pom[pocz];
                for(int i = pocz + 1; i <= min(b, pocz + niewziete); i++)
                    DP[i] = max(DP[i - 1], DP[i - k] + pom[i]);
                
                pocz += k;
            }
            ans[query] = DP[b];
        }
    }

#ifdef DEBUG
    cerr << "MALE: " << male << ", DUZE: " << duze << ", SREDNIA DLUGOSC " << dlugosci / q << endl;
    cerr << "MINELO " << setprecision(3) << fixed << clock() / (long double)CLOCKS_PER_SEC << " SEKUND " << endl;
    int losowania = 0;
#endif

#ifndef BEZ_RANDA
    do{ // Pora na sztuczki!
        int przed = losuj(2, n - 1);
        if(used_as_przed[przed])
            continue; // tu sie może zrobić ciasno, ale to nic złego
        used_as_przed[przed] = true;
        #ifdef DEBUG
        losowania ++;
        #endif

        // robimy DP w prawo od miejsca przed
        // i w lewo od miejsca przed - 1

        for(int i = przed - 1; i <= min(n, przed + k - 2); i++)
            DP[i] = 0;
        for(int i = przed + k - 1; i <= n; i++)
            DP[i] = max(DP[i - 1], pom[i] + DP[i - k]);

        for(int i = przed - 1; i >= max(1, przed - k + 1); i--)
            DP[i] = 0;
        if(przed - k >= 1)
            DP[przed - k] = max(0LL, pom[przed - 1]);
        for(int i = przed - k - 1; i >= 1; i--)
            DP[i] = max(DP[i + 1], pom[i + k - 1] + DP[i + k]);

        for(int i = 0; i < q; i++)
            if(queries[i].f < przed and queries[i].s >= przed)
                ans[i] = max(ans[i], DP[queries[i].f] + DP[queries[i].s]);

    }while(clock() < CLOCK_LIMIT * CLOCKS_PER_SEC); // około 30 sekund
    
    #ifdef DEBUG
    cerr << "LOSOWANIA " << losowania << endl;
    #endif

    for(int i = 0; i < q; i++)
        cout << ans[i] << '\n';
#endif
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int tests = 1;
    // cin >> tests;

    for (int i = 0; i < tests; i++)
        solve();

    return 0;
}