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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <cstdio> 
#include <cinttypes>
#include <algorithm>
#include <vector>
#include <cassert>

#define MAXN 300300
// How many queries should there be for us to just manual solve.
#define LIMIT 1

typedef long long ll;

ll data[MAXN];   

int queryL[MAXN];
int queryR[MAXN];
ll queryAns[MAXN];

int N, K, Q;

ll dyn[MAXN];

ll prevdyn(int L, int i) {
  if (i < L) return 0;
  return dyn[i];
}

ll dynrev[MAXN];

ll nextdyn(int R, int i) {
  if (i > R) return 0;
  return dynrev[i];
}

ll manualSolve(int L, int R) {
  ll curr = 0;
  for (int i = L; i < R; ++i) {
    dyn[i] = prevdyn(L, i-1);
    curr += data[i];
    if (i-K >= L) {
      curr -= data[i-K];
    }
    if (i-K >= L-1) {
      dyn[i] = std::max(dyn[i], prevdyn(L, i-K) + curr);
    }
  }
  return dyn[R-1];
}

// R inclusive, L exclusive.
ll reverseSolve(int R, int L) {
  ll curr = 0;
  for (int i = R; i > L; --i) {
    dynrev[i] = nextdyn(R, i+1);
    curr += data[i]; 
    if (i+K <= R) curr -= data[i+K];
    if (i+K <= R+1) dynrev[i] = std::max(dynrev[i], nextdyn(R, i+K) + curr); 
  } 
  return dynrev[L+1];
}

// R is exclusive, L is inclusive.
void solveAllRecursive(int L, int R, const std::vector<int> &queries) {
  int beg = (R + L - K) / 2; // The first split. 
  int end = beg + K;  // The first non-split.
  // Split is the last thing on the left when we split.
  if (beg < L || end > R) {
    for (int q : queries) {
//fprintf(stderr, "Doing manual solve for query %d\n", q);
      assert(queryL[q] >= L);
      assert(queryR[q] <= R);
      queryAns[q] = manualSolve(queryL[q], queryR[q]);
    }
    return;
  } 
  std::vector<int> leftside;
  std::vector<int> rightside;
  std::vector<int> solvable;
  for (int q : queries) {
    if (queryL[q] > end) {
      rightside.push_back(q);
    } else if (queryR[q] <= beg) {
      leftside.push_back(q); 
    } else {
//fprintf(stderr, "Query %d [%d, %d] is solvable in [%d, %d) (splits [%d,%d])\n", q, queryL[q], queryR[q], L, R, beg, end);
      solvable.push_back(q);
    }
  }
//fprintf(stderr, "Splits in [%d, %d)\n", beg, end);
  assert (beg >= L);
  assert (end < R);
  // Split is the thing that lands on the left.
  if (!solvable.empty()) for (int split = beg; split < end; ++split) {
    manualSolve(split + 1, R);
    reverseSolve(split, L-1);
    for (int q : solvable) {
      if (queryL[q] <= split + 1 && queryR[q] > split) {
        queryAns[q] = std::max(queryAns[q], prevdyn(split + 1, queryR[q] - 1) + nextdyn(split, queryL[q])); 
//fprintf(stderr, "After analysing split at %d, the query has answer %I64d\n", split, queryAns[q]);
      } 
    }
  }   
  if (!leftside.empty()) solveAllRecursive(L, beg, leftside);
  if (!rightside.empty()) solveAllRecursive(end + 1, R, rightside);   
}

int main() {
  scanf("%d %d %d", &N, &K, &Q);
  for (int i = 0; i < N; ++i) {
    int temp; scanf("%d", &temp); data[i] = temp;
  }
  for (int i = 0; i < Q; ++i) {
    scanf("%d %d", &queryL[i], &queryR[i]);
    queryL[i] -= 1;
    queryAns[i] = -1;
  }
// Manual solve all queries.
//  for (int q = 0; q < Q; ++q) {
//    queryAns[q] = manualSolve(queryL[q], queryR[q]);
//  }


// Manual reverse solve for all queries.
//  for (int q = 0; q < Q; ++q) {
//    queryAns[q] = reverseSolve(queryR[q] - 1, queryL[q] - 1);
//  }

// Solve for small K.
  std::vector<int> queries;  
  for (int i = 0; i < Q; ++i) queries.push_back(i);
  solveAllRecursive(0, N, queries);
  
  for (int q = 0; q < Q; ++q) printf("%" PRId64 "\n", queryAns[q]);
}