题目描述

题目译自 PA 2021 Runda 5 Desant 2

为防止测评占用时间过长，将原时限 42s 下调至 10s。

Byteotia 准备再次袭击 Bitotia！在敌人的领土上登陆是一个真正硬汉的任务，因此，Byteotia 最好的特种部队的士兵——Byteburg——将参与其中。

Bytchak 将军让 $n$ 名士兵集合，由于多年的演习训练，他们立即排成一排，并从左到右用 $1$ 到 $n$ 的整数编号。将军希望选择一定数量的部队重新部署到 Bitotia 境内。作为一个熟练的战略家，他知道他的部下排队顺序不是随意的，而是与他们之间的友好关系有关，所以他选择的每支部队必须恰好由 $k$ 个连续的士兵组成。通过这种方式，他可以确保组成小队的士兵能够很好地合作。当然，每个士兵最多属于一个小队，将军对小队的数量没有偏好——特别是，他可以不选择任何小队而放弃对 Bitotia 的攻击（至少暂时如此）。

Bytchak 将军知道每一个士兵的技能——他可以用一个整数 $a_i$ 来描述他们每个人。技能值越高，这个士兵在战斗中的效率就越高。这个值也可以是负数，意味着这个士兵可能只会阻碍行动。

将军希望将所有将被派去登陆的士兵的 $a_i$ 值之和最大化。然而，有一个问题。可能他要派一定数量的排头兵去与 Intotia 作战的前线，而派一定数量的排尾兵在 Longlongotia 进行情报行动。那么他将不得不只从位置号在 $[l_i, r_i]$ 范围内的士兵中选择部队。

帮助将军考虑不同的情况，并为每一种情况计算派去登陆的士兵的最大可能的 $a_i$ 值之和。

输入格式

第一行三个整数 $n,k,q\ (1\le n,q\le 3\cdot 10^5,1\le k\le n)$，分别表示士兵总数，每支队伍中士兵人数和将军考虑的情况数。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n\ (-10^9\le a_i\le 10^9)$，表示每个士兵的技能值。

接下来 $q$ 行，每行两个整数 $l_i,r_i\ (1\le l_i\le r_i\le n)$。表示第 $i$ 种情况，只有编号在 $[l_i,r_i]$ 范围内的士兵参与对 Bitotia 的作战。

输出格式

输出 $q$ 行，第 $i$ 行包含一个整数，表示在第 $i$ 种情况下参与作战的士兵最大的技能值之和。

8 3 7
3 -1 10 0 10 -1 1 -1
1 8
3 5
6 8
1 2
1 7
2 8
1 6

22
20
0
0
22
20
21

数据范围与提示

存在一些子任务满足 $k\le 30$。