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
#pragma GCC optimize ("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define FOR(i, a, b) for (auto i=(a); i<(b); i++)
#define FORD(i, a, b) for (int i=(a); i>(b); i--)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define PPC(x) __builtin_popcountll(x)
#define MSB(x) (63 - __builtin_clzll(x))
#define LSB(x) __builtin_ctz(x)
#define ARG(x, i) (get<i>(x))
#define ithBit(m, i) ((m) >> (i) & 1)
#define pb push_back
#define ft first
#define sd second
#define kw(a) ((a) * (a))
#ifdef DEBUG
#include "debug.h"
#else
#define dbg(...) 0
#endif
using namespace std; 

template <typename T1, typename T2> inline void remin(T1& a, T2 b) { a = min(a, (T1)b);	}
template <typename T1, typename T2> inline void remax(T1& a, T2 b) { a = max(a, (T1)b);	}

using Ky = vector <int>;

const int maxN = 1 << 19;
const long long INF = 1'0000'0000'0000'0000;

long long Left[maxN], Right[maxN], prefL[maxN], prefR[maxN];
int k;

void calc(long long dp[maxN], int* T, int n, int x, long long pref[maxN])
{
	int s = min(x, n+1);
	FOR(i, 0, s)
		dp[i] = -INF;
	s = min(k, n+1);
	FOR(i, x, s)
		dp[i] = pref[x];
	FOR(i, k, n+1)
		dp[i] = max(dp[i-1], dp[i-k] + pref[i]-pref[i-k]);
}

pair <int, int> Q[maxN];
long long res[maxN];

void go(int* T, int n, vector <int>& qs)
{
	if (qs.empty() or n <= k)
		return;
	
	int n1 = n/2, n2 = n - n1, *T2 = T + n1;	
	vector <int> l, r, mid;
	for (int i : qs)
	{
		auto [a, b] = Q[i];
		if (b <= n1)
			l.pb(i);
		else if (a > n1)
		{
			Q[i] = {a - n1, b - n1};
			r.pb(i);
		}
		else
		{
			Q[i] = {n1 - a + 1 , b - n1};
			mid.pb(i);
		}
	}
	
	#define SPLIT(x, y) \
	{ \
		calc(Left, T, n1, x, prefL); calc(Right, T2, n2, y, prefR); \
		for (int i : mid)  remax(res[i], Left[Q[i].ft] + Right[Q[i].sd]); \
	}
	
	reverse(T+1, T+n1+1);
	
	FOR(i, 1, n1+1)	prefL[i] = prefL[i-1] + T[i];
	FOR(i, 1, n2+1)	prefR[i] = prefR[i-1] + T2[i];
	
	SPLIT(0, 0);
	FOR(j, 1, k)
		SPLIT(j, k-j);
	reverse(T+1, T+n1+1);	
	
	go(T, n1, l);
	go(T2, n2, r);
}

int T[maxN];

void solve()
{
	int n, q;
	scanf ("%d%d%d", &n, &k, &q);
	FOR(i, 1, n+1)
		scanf ("%d", T+i), prefR[i] = prefR[i-1] + T[i];
	FOR(i, 0, q)
	{
		int a, b;
		scanf ("%d%d", &a, &b);
		if ((b-a+1) % k == 0)
			remax(res[i], prefR[b] - prefR[a-1]);
		Q[i] = {a, b};
	}
	vector <int> qs(q);
	iota(ALL(qs), 0);
	go(T, n, qs);
	FOR(i, 0, q)
		printf("%lld\n", res[i]);	
}
 
int main()
{
	int t = 1;
	//scanf ("%d", &t);
	FOR(tid, 1, t+1)
	{
		//printf("Case #%d: ", tid);
		solve();
	}
	return 0;
}