#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <array>
#include <random>
#include <cmath>
#include <chrono>
#include <list>
#include <ctime>
#include <sstream>
#include <queue>
#include <climits>
#include <stack>
#include <valarray>
#include <random>
#include <bitset>
#include <numeric>
#include <iomanip>
#include <cassert>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
#define rep(x, b, e) for(int x=(b); x<(e); ++x)
#define trav(a, x) for(auto& a : x)
#define ford(x, b, e) for(int x=((int)(b))-1; x>=(e); --x)
#define all(c) c.begin(),c.end()
#define sz(x) ((int)((x).size()))
#define pb push_back
#define eb emplace_back
#define st first
#define nd second
#define mp(x,y) make_pair(x,y)
typedef short int sint;
template<typename T> bool ckmin(T& a, const T& b){return b<a?a=b,1:0;}
template<typename T> bool ckmax(T& a, const T& b){return b>a?a=b,1:0;}


template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(char c) {
  return string(1, c);
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif


// #include <atcoder/modint>
// using namespace atcoder;
// using mint = modint998244353; // modint1000000007;
// typedef vector<mint> vmi;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // use rng() to get unsigned int
// mt19937_64 for random long longs

const int N = 3e5 + 10;
const int BRUT = 1e4;
const int SMALL_K = 3e3+1;
ll a[N];
ll res[N]; // query res
pii qs[N];
ll brutArray[BRUT + 10];
int n, k, q;
ll h[2][N];

ll bru(int p, int q) {
  brutArray[0] = max(0ll, a[p]);
  rep(i, 1, k) {
    brutArray[i] = max(brutArray[i - 1], a[i + p]);
  }
  rep(i, k, q - p) {
    brutArray[i] = max(brutArray[i - 1], a[i + p] + brutArray[i - k]);
  }
  return brutArray[q - p - 1];
}

void compute(int p, int q, const vi& hard) {
  if (sz(hard) == 0) return;
  int sr = (p + q) / 2;
  vi left, right;
  vi here;
  for (auto q_i : hard) {
    if (qs[q_i].nd <= sr) {
      left.pb(q_i);
    } else if (qs[q_i].st >= sr) {
      right.pb(q_i);
    } else {
      here.pb(q_i);
    }
  }
  compute(p, sr, left);
  compute(sr, q, right);
  rep(diff, 0, k) {
    // left starting from sr - k + i
    // right mast start from: sr + i
    int rStart = sr + diff;
    int lStart = sr - k + diff;
    bool rok = false, lok = false;
    if (rStart < n) {
      rok = true;
      h[1][0] = max(0ll, a[rStart]);
      rep(i, rStart + 1, q) {
        int idx = i - rStart;
        if (idx < k) {
          h[1][idx] = max(h[1][idx - 1], a[i]);
        } else {
          h[1][idx] = max(h[1][idx - 1], a[i] + h[1][idx - k]);
        }
      }
    }
    if (lStart >= 0) {
      lok = true;
      h[0][0] = max(0ll, a[lStart]);
      ford(i, lStart, p) {
        int idx = lStart - i;
        if (idx < k) {
          h[0][idx] = max(h[0][idx - 1], a[i]);
        } else {
          h[0][idx] = max(h[0][idx - 1], a[i] + h[0][idx - k]);
        }
      }
    }
    // debug("compute", p, q, here, sr);
    // debug(diff, lStart, lok, rStart, rok);
    for (auto h_i : here) {
      int l = qs[h_i].st;
      int r = qs[h_i].nd;
      if (lok && rok && l <= lStart && r > rStart) {
        ckmax(res[h_i], h[0][lStart - l] + h[1][r - rStart - 1]);
      }
      if (lok && l <= lStart) {
        ckmax(res[h_i], h[0][lStart - l]);
      }
      if (rok && r > rStart) {
        ckmax(res[h_i], h[1][r - rStart - 1]);
      }
    }
  }
}

void solve() {
  scanf("%d %d %d", &n, &k, &q);
  rep(i, 0, n) {
    scanf("%lld", &a[i]);
  }
  ll s = 0;
  rep(i, 0, k - 1) {
    s += a[i];
  }
  rep(i, k - 1, n) {
    s += a[i];
    ll rem = a[i - k + 1];
    a[i - k + 1] = s;
    s -= rem;
  }
  n -= (k - 1);
  // rep(i, 0, n) {
  //   printf("%lld ", a[i]);
  // }
  // printf("\n");
  vi hard;
  rep(i, 0, q) {
    scanf("%d %d", &qs[i].st, &qs[i].nd);
    if (qs[i].nd - qs[i].st + 1 < k) {
      continue;
    }
    --qs[i].st;
    qs[i].nd -= (k - 1);
    debug(qs[i]);
    int len = qs[i].nd - qs[i].st;
    if (len <= BRUT) {
      res[i] = bru(qs[i].st, qs[i].nd);
    } else {
      hard.pb(i);
    }
  }
  compute(0, n, hard);
  rep(i, 0, q) {
    printf("%lld\n", res[i]);
  }
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int t;
	// cin >> t;
	t = 1;
	while (t--) {
		solve();
	}
}