{"raw_statement":[{"iden":"statement","content":"Byteotia 准备再次袭击 Bitotia！在敌人的领土上登陆是一个真正硬汉的任务，因此，Byteotia 最好的特种部队的士兵——Byteburg——将参与其中。\n\nBytchak 将军让 $n$ 名士兵集合。他们立即排成一排，并从左到右依次用 $1$ 到 $n$ 的整数编号。将军希望选择一定数量的部队重新部署到 Bitotia 境内。作为一个熟练的战略家，他知道他的部下排队顺序不是随意的，而是与他们之间的友好关系有关，所以他选择的每支部队必须恰好由 $k$ 个连续的士兵组成。通过这种方式，他可以确保组成小队的士兵能够很好地合作。当然，每个士兵最多属于一个小队，将军对小队的数量没有偏好——特别是，他可以不选择任何小队而放弃对 Bitotia 的攻击（至少暂时如此）。\n\nBytchak 将军知道每一个士兵的技能——他可以用一个整数 $a_i$ 来描述他们每个人。技能值越高，这个士兵在战斗中的效率就越高。这个值也可以是负数，意味着这个士兵可能只会阻碍行动。\n\n将军希望将所有将被派去登陆的士兵的 $a_i$ 值之和最大化。然而，有一个问题。可能他要派一定数量的排头兵去与 Intotia 作战的前线，而派一定数量的排尾兵在 Longlongotia 进行情报行动。那么他将不得不只从位置号在 $[l_i, r_i]$ 范围内的士兵中选择部队。\n\n请你帮助将军考虑不同的情况，并为每一种情况计算派去登陆的士兵的最大可能的 $a_i$ 值之和。"},{"iden":"input","content":"第一行，三个整数 $n, k, q$，分别表示士兵总数、每支队伍中士兵人数和将军考虑的情况数；\n\n第二行，$n$ 个整数 $a_1, a_2, \\cdots, a_n$，表示每个士兵的技能值；\n\n接下来 $q$ 行，其中第 $i$ 行有两个整数 $l_i, r_i$，表示第 $i$ 种情况，即只有编号在 $[l_i, r_i]$ 范围内的士兵参与对 Bitotia 的作战。"},{"iden":"output","content":"$q$ 行，其中第 $i$ 行一个整数，表示在第 $i$ 种情况下参与作战的士兵最大的技能值之和。"},{"iden":"note","content":"对于 $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$。"}],"translated_statement":null,"sample_group":[["8 3 7\n3 -1 10 0 10 -1 1 -1\n1 8\n3 5\n6 8\n1 2\n1 7\n2 8\n1 6","22\n20\n0\n0\n22\n20\n21"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}