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

#define FOR(i, n) for (int i = 0; i < int(n); ++i)
#define FO(i, a, b) for (int i = (a); i < int(b); ++i)
#define OF(i, a, b) for (int i = (b)-1; i >= int(a); --i)

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((b) < (a) ? (a) : (b))

#define REMIN(a, b) ((a) = min(a, b))
#define REMAX(a, b) ((a) = max(a, b))

#define ALL(c) (c).begin(), (c).end()

#define SQR(x) ((x) * (x))

#define PRINT(x) cerr << #x << " == " << x << endl;

#define ZERO(x) memset(x, 0, sizeof(x));

#define endl '\n'

using LL = long long;
using LD = long double;

#define ASS(x)                                                                 \
  if (!(x)) {                                                                  \
    cerr << "ASSERT FAILED " #x << " " << __FILE__ << ':' << __LINE__ << endl; \
    abort();                                                                   \
  }

//

const bool READ_NUM_TEST_CASES = false;

const int N = 300'000 + 9;
const int NN = 1024 * 512;

const int K_SPLIT = 79;

int n, k, q;
int arr[N];
LL sums[N];

struct Block {
  LL res[K_SPLIT][K_SPLIT];

  Block() { ZERO(res); }
};

struct PartialBlock {
  LL res[K_SPLIT];
};

PartialBlock merge(const PartialBlock &a, const Block &b, int b_size) {
  PartialBlock r;
  FOR(i, k) {
    LL best = 0;
    if (i + b_size < k)
      REMAX(best, a.res[i + b_size]);

    FOR(j, min(k, b_size + 1)) {
      LL cand = a.res[j] + b.res[j][i];
      // if (cand == 10)
      //   cerr << "aaaaa " << j << " " << i << " " << a.res[j] << " "
      //        << b.res[j][i] << endl;
      REMAX(best, cand);
    }
    r.res[i] = best;
  }
  return r;
}

struct Query {
  int l, r;

  PartialBlock pb;
  bool once = false;
};
vector<Query> queries;

struct Range {
  int fr;
  int to;
  bool operator<(const Range &o) const {
    return pair{fr, -to} < pair{o.fr, -o.to};
  }
};
multimap<Range, int> qs;

void build_tree_rec(int v, int a, int b) {
  // cerr << "build_tree_rec " << v << " " << a << " " << b << endl;
  // ASS(a + 1 <= b);
  // ASS(v >= 1);

  int mid = (a + b) / 2;

  if (qs.empty())
    return;

  auto p = qs.begin()->first;

  ASS(p.fr >= a);

  if (p.fr <= a && b <= p.to) {
    Block bl;
    FOR(k0, k) {
      int dp_size = b + k - (a + k0) + 1;
      LL dp[dp_size];
      dp[0] = 0;
      FO(i, a + k0, min(n, b + k)) {
        int idx = i - (a + k0) + 1;

        ASS(idx >= 0 && idx < dp_size);

        dp[idx] = dp[idx - 1];
        if (idx - k >= 0) {
          REMAX(dp[idx], dp[idx - k] + sums[i]);
        }

        int tail = i - (b - 1);
        if (tail >= 0 && tail < k) {
          bl.res[k0][tail] = dp[idx];
        }
      }
    }

    while (!qs.empty()) {
      p = qs.begin()->first;
      ASS(p.fr >= a);
      if (!(p.fr <= a && b <= p.to))
        break;

      // cerr << "process " << p.fr << " " << p.to << endl;

      int i_query = qs.begin()->second;
      auto &query = queries[i_query];
      if (query.once) {
        query.pb = merge(query.pb, bl, b - a);
      } else {
        query.once = true;
        FOR(kk, k) query.pb.res[kk] = bl.res[0][kk];
      }

      query.l += b - a;
      ASS(query.l <= query.r);

      qs.erase(qs.begin());

      if (query.l < query.r)
        qs.insert({{query.l, query.r}, i_query});
    }
  }

  if (qs.empty())
    return;

  p = qs.begin()->first;
  ASS(p.fr < p.to);

  ASS(!(p.fr <= a && b <= p.to));

  if (p.fr < mid) {
    build_tree_rec(v * 2, a, mid);

    if (qs.empty())
      return;

    p = qs.begin()->first;
  }

  if (p.fr < b) {
    build_tree_rec(v * 2 + 1, mid, b);
  }

  if (qs.empty())
    return;

  p = qs.begin()->first;
  ASS(p.fr >= b);
}

void build_tree() {
  FOR(i, q) { qs.insert({{queries[i].l, queries[i].r}, i}); }
  build_tree_rec(1, 0, NN);
}

void clean() {
  // ZERO(arr);
  //
}

void solve() {
  cin >> n >> k >> q;

  FOR(i, n) { cin >> arr[i]; }

  sums[0] = arr[0];
  FO(i, 1, n) {
    sums[i] = sums[i - 1] + arr[i];
    if (i - k >= 0)
      sums[i] -= arr[i - k];
  }

  // cerr << "sums ";
  // FOR(i, 20) cerr << sums[i] << " ";
  // cerr << endl;

  // cerr << "TEST ";
  // FOR(i, 8) cerr << tree[1].res[i][0] << " ";
  // cerr << endl;

  FOR(qq, q) {
    int l, r;
    cin >> l >> r;
    --l;
    // --r;

    Query qqq;
    qqq.l = l;
    qqq.r = r;
    queries.push_back(qqq);
  }

  build_tree();

  FOR(qq, q) {
    ASS(queries[qq].l == queries[qq].r);
    cout << queries[qq].pb.res[0] << endl;
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cout.precision(20);
  cout << fixed;

  int num_cases = 1;
  if (READ_NUM_TEST_CASES)
    cin >> num_cases;

  FOR(i, num_cases) {
    clean();
    solve();
  }

  return 0;
}