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
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

const int nax = 300 * 1000 + 10;
int n, k, q;
ll a[nax];
pi qrs[nax];
ll dpl[nax], dpr[nax];
ll ans[nax];

void run_dpl(int l, int r) {
	dpl[r + 1] = 0;
	for(int i = r; i >= l; --i) {
		dpl[i] = dpl[i + 1];
		if(i + k - 1 <= r) {
			dpl[i] = max(dpl[i], dpl[i + k] + a[i + k - 1] - a[i - 1]);
		}
	}
}

void run_dpr(int l, int r) {
	dpr[l - 1] = 0;
	for(int i = l; i <= r; ++i) {
		dpr[i] = dpr[i - 1];
		if(i - k + 1 >= l) {
			dpr[i] = max(dpr[i], dpr[i - k] + a[i] - a[i - k]);
		}
	}
}

void rec(int l, int r, vi v) {
	int mid = (l + r) / 2;
	if(r - l + 1 < k) return;
	vi vl, vr, here;
	for(int x : v) {
		if(qrs[x].ND < mid) {
			vl.PB(x);
		} else if(qrs[x].ST > mid) {
			vr.PB(x);
		} else {
			here.PB(x);
		}
	}
	if(l < mid) rec(l, mid - 1, vl);
	if(mid < r) rec(mid + 1, r, vr);
	for(int i = max(l, mid - k + 1); i <= mid && i + k - 1 <= r; ++i) {
		ll sum = a[i + k - 1] - a[i - 1];
		run_dpl(l, i - 1);
		run_dpr(i + k, r);
		for(int x : here) {
			if(qrs[x].ST <= i && i + k - 1 <= qrs[x].ND) {
				ans[x] = max(ans[x], dpl[qrs[x].ST] + sum + dpr[qrs[x].ND]);
			}
		}
	}
	run_dpl(l, mid);
	run_dpr(mid + 1, r);
	for(int x : here) {
		ans[x] = max(ans[x], dpl[qrs[x].ST] + dpr[qrs[x].ND]);
	}
}


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k >> q;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		a[i] += a[i - 1];
	}
	vi v(q);
	for(int i = 0; i < q; ++i) {
		cin >> qrs[i].ST >> qrs[i].ND;
		v[i] = i;
	}
	rec(1, n, v);
	for(int i = 0; i < q; ++i) {
		cout << ans[i] << "\n";
	}
}