#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
// ll mod = 1e9+7;
// ll mod = 998244353;
// ll mod = 999999937;
// 1 

struct Q {
    int l, r, i; //[l, r] and index of query
    int64_t o;
};

inline int64_t hilbertOrder(int x, int y, int pow, int rotate) {
    if (pow == 0) {
        return 0;
    }
    int hpow = 1 << (pow-1);
    int seg = (x < hpow) ? (
            (y < hpow) ? 0 : 3
    ) : (
                      (y < hpow) ? 1 : 2
              );
    seg = (seg + rotate) & 3;
    const int rotateDelta[4] = {3, 0, 0, 1};
    int nx = x & (x ^ hpow), ny = y & (y ^ hpow);
    int nrot = (rotate + rotateDelta[seg]) & 3;
    int64_t subSquareSize = int64_t(1) << (2*pow - 2);
    int64_t ans = seg * subSquareSize;
    int64_t add = hilbertOrder(nx, ny, pow-1, nrot);
    ans += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
    return ans;
}

void sol(){
    
    ll n;
    cin >> n;

    ll k;
    cin >> k;

    vector<ll> v(n);
    for (ll i = 0; i < n; i++) {
        cin >> v[i];
        if (v[i] < 0) v[i] = 0;
    }

    ll q;
    cin >> q;
    vector<Q> query(q);
    vector<ll> ans(q);

    for (ll i = 0; i < q; i++) {
        ll l, r;
        cin >> l >> r;
        l--;
        r--;
        query[i].l = l;
        query[i].r = r;
        query[i].i = i;
        query[i].o = hilbertOrder(l, r, 20, 0);
    }

    auto cmp = [&] (Q& v1, Q &v2) -> bool {
        return v1.o < v2.o;
    };
    sort(query.begin(), query.end(), cmp);

    multiset<ll> st1, st2;
    ll sum = 0;

    auto ADD = [&](ll x) -> void {
        if ((ll)st2.size() < k) {
            st2.insert(x);
            sum += x;
        } 
        else if ((!st2.empty()) && *st2.begin() < x) {
            sum += x - *st2.begin();
            st1.insert(*st2.begin());
            st2.erase(st2.begin());
            st2.insert(x);
        }
        else st1.insert(x);
    };

    auto REMOVE = [&](ll x) -> void {
        if (st1.find(x) != st1.end()) st1.erase(st1.find(x));
        else if (st2.find(x) != st2.end()) {
            sum -= x;
            st2.erase(st2.find(x));
            if (!st1.empty()) {
                ll newMax = *st1.rbegin();
                st2.insert(newMax);
                st1.erase(--st1.end());
                sum += newMax;
            }
        }
    };

    int l = 0, r = -1;
    for (auto &it : query) {
        while (r < it.r) {
            ADD(v[++r]);
        }
        while (r > it.r) {
            REMOVE(v[r--]);
        }
        while (l < it.l) {
            REMOVE(v[l++]);
        }
        while (l > it.l) {
            ADD(v[--l]);
        }

        ans[it.i] = sum;
    }

    for (auto it : ans) cout << it << endl;

}
 
int main(){

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout.tie(nullptr);

    ll t = 1;
    // cin >> t;
    while(t--) sol();
    return 0;

}