Bajtocja 计划再次进攻 Bitocja！对敌方领土的空降作战是真正的硬汉任务，因此 Bajtocja 最好的特种部队——Bajtogrom 将参与其中。

在 Bajtczak 将军的简报会上，集结了 $n$ 名士兵。由于多年的操练，他们迅速排成一列，因此可以从左到右用 $1$ 到 $n$ 的整数对他们进行编号。将军希望挑选若干个小队投入 Bitocja 的领土。

作为一名经验丰富的战略家，他知道下属们以这种顺序排列并非没有原因，而是因为他们之间存在友谊关系。因此，他挑选的每个小队必须由恰好 $k$ 名占据队列中连续位置的士兵组成。这样他就能确信，组成小队的士兵们会很好地协作。当然，每名士兵最多只能属于一个小队，但将军对小队的数量没有任何偏好——特别地，他也可以选择不挑选任何小队，暂时放弃对 Bitocja 的进攻。

Bajtczak 将军了解他士兵的能力——他可以用一个整数 $a_i$ 来描述每名士兵。该数值越高，士兵在战斗中就越强。这个数字也可能是负数，这意味着该士兵可能会阻碍行动。

将军希望最大化所有被派往空降作战的士兵的 $a_i$ 值之和。然而，这里有一个陷阱。可能会发生这样的情况：他必须将队列中前若干名士兵派往与 Intocja 的前线，并将队列中最后若干名士兵派往 Longlongtocja 执行侦察任务。在这种情况下，他只能在位置编号位于区间 $[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, \dots, a_n$ ($-10^9 \le a_i \le 10^9$)，即题目描述中提到的士兵能力值。

接下来的 $q$ 行，每行包含两个整数。第 $i$ 行包含 $l_i$ 和 $r_i$ ($1 \le l_i \le r_i \le n$)。这意味着在第 $i$ 个场景中，只能派遣位置编号在区间 $[l_i, r_i]$ 内的士兵。

输出格式

输出应包含 $q$ 行。第 $i$ 行应包含一个整数，表示在第 $i$ 个场景中派往 Bitocja 的士兵的 $a_i$ 值之和的最大值。

样例

输入 1

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

输出 1

22
20
0
0
22
20
21

说明 1

在第一个和第五个场景中，Bajtczak 将军应该派遣两个小队，分别由占据位置 $[1, 2, 3]$ 和 $[5, 6, 7]$ 的士兵组成。

在第二个和第六个场景中，最优方案是仅创建一个由占据位置 $[3, 4, 5]$ 的士兵组成的小队。

在第三个和第四个场景中，将军不应创建任何小队，并冷静地重新考虑整个进攻计划。

在第七个场景中，将军应该创建两个小队，分别由占据位置 $[1, 2, 3]$ 和 $[4, 5, 6]$ 的士兵组成。

子任务

在某些测试组中，满足 $k \le 30$。