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
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
#ifdef _MSC_VER
  #ifndef __GNUC__
    #pragma warning(disable: 4996)
  #endif
  #define main main0
#endif
#include <algorithm>
#include <iomanip>
#include <iostream>
using namespace std;
typedef long long           ll;
typedef unsigned long long ull;
typedef unsigned int      uint;

ll oddzial[300005];
ll suma_ai[300005];
ll aiPrzypadku[300005];
ll zolnierz[300005];
ll dodane[300005];

void Drukuj(int n) {
  cout << '\n' << " nr zolnierz  oddzial  sumaMax dodane\n";
  for(int i = 1; i <= n; ++i)
    cout << setw(2) << i << setw(9) << zolnierz[i] << setw(9) << oddzial[i] << setw(9) << suma_ai[i] << setw(3) << dodane[i] << '\n';
  cout << endl;
}/**/

void ObliczCalosc(int n, int k) {
  ll suma = 0;
  int j;

  fill_n(oddzial, k, 0);
  fill_n(suma_ai, k, 0);
  for(int i = 1; i <= n; ++i)
    cin >> zolnierz[i];

  for(j = 1; j <= k; ++j)
    suma += zolnierz[j];
  oddzial[k] = suma > 0 ? suma: 0;
  for( ; j <= n; ++j) {
    suma += zolnierz[j] - zolnierz[j-k];
    oddzial[j] = suma > 0 ? suma : 0;
  }

  suma_ai[k] = oddzial[k];
  for(j = k + 1; j <= n && (suma_ai[j-k] == 0); ++j) {
    suma_ai[j] = oddzial[j] >= suma_ai[j-1] ? oddzial[j] : suma_ai[j-1];
//    dodane[j] = suma_ai[j]-suma_ai[j-1];
  }
  for( ; j <= n; ++j) {
    suma = oddzial[j] + suma_ai[j-k];
    suma_ai[j] = suma_ai[j-1] > suma ? suma_ai[j-1] : suma;
//    dodane[j] = suma_ai[j]-suma_ai[j-1];
  }
}

void ObliczPrzypadek(int k, int l, int r) {
  int j;
  ll suma1 = 0;
  fill_n(aiPrzypadku + l, k, 0);
  l += k - 1;
  aiPrzypadku[l] = oddzial[l];
  for(j = l + 1; j <= r && (aiPrzypadku[j-k] == 0); ++j) {
    aiPrzypadku[j] = oddzial[j] >= aiPrzypadku[j-1] ? oddzial[j] : aiPrzypadku[j-1];
    dodane[j] = aiPrzypadku[j]-aiPrzypadku[j-1];
  }
  for( ; j <= r; ++j) {
    suma1 = oddzial[j] + aiPrzypadku[j-k];
    aiPrzypadku[j] = aiPrzypadku[j-1] > suma1 ? aiPrzypadku[j-1] : suma1;
    dodane[j] = aiPrzypadku[j]-aiPrzypadku[j-1];
  }
//  Drukuj(r);
}

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

  int n, k, q;
  ll suma1 = 0;

  cin >> n >> k >> q;
  ObliczCalosc(n, k);
//  Drukuj(n);

  for(int i = 0; i < q; ++i) {
    int l, r;
    cin >> l >> r;
    if(r - l < k - 1)
      cout << '0' << '\n';
    else if(r - l == k - 1)
      cout << oddzial[r] << '\n';
    else {
      ObliczPrzypadek(k, l, r);
//    Drukuj(n);
      cout << aiPrzypadku[r] << endl;
    }
  }

  return 0;
}