题目描述

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$，分别表示士兵总数、每支队伍中士兵人数和将军考虑的情况数；

第二行，$n$ 个整数 $a_1, a_2, \cdots, a_n$，表示每个士兵的技能值；

接下来 $q$ 行，其中第 $i$ 行有两个整数 $l_i, r_i$，表示第 $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

提示

对于 $100\%$ 的数据，$1 \leq n, q \leq 3 \times 10^5$，$1 \leq k \leq n$，$-10^9 \leq a_i \leq 10^9$，$1 \leq l_i \leq r_i \leq n$。