바이트치아는 다시 한번 비토치아를 공격할 계획을 세우고 있습니다! 적진에 대한 강습은 진정한 강자들만이 수행할 수 있는 임무이기에, 바이트치아 최고의 특수부대인 '바이트그롬'의 병사들이 투입될 예정입니다.

바이트차크 장군의 브리핑에는 $n$명의 병사가 모였습니다. 이들은 수년간의 훈련 덕분에 즉시 일렬로 정렬하였고, 왼쪽부터 오른쪽으로 $1$부터 $n$까지의 정수로 번호를 매길 수 있게 되었습니다. 장군은 비토치아 영토로 투입할 여러 부대를 선발하고자 합니다.

노련한 전략가인 장군은 부하들이 아무 이유 없이 정렬한 것이 아니라 서로 간의 친분 관계를 고려하여 섰다는 것을 알고 있습니다. 따라서 장군이 선택하는 각 부대는 반드시 정렬된 위치에서 연속된 구간을 차지하는 정확히 $k$명의 병사로 구성되어야 합니다. 이를 통해 부대로 묶인 병사들이 서로 잘 협력할 것임을 확신할 수 있습니다. 물론 각 병사는 최대 하나의 부대에만 속할 수 있지만, 장군은 부대의 수에 대해서는 아무런 제한을 두지 않습니다. 특히, 부대를 하나도 선택하지 않고 비토치아 공격을 포기할 수도 있습니다(적어도 당분간은 말입니다).

바이트차크 장군은 병사들의 능력을 알고 있으며, 각 병사를 정수 $a_i$로 나타낼 수 있습니다. 이 값이 클수록 해당 병사는 전투 능력이 뛰어납니다. 이 값은 음수일 수도 있는데, 이는 해당 병사가 작전에 방해만 될 가능성이 높음을 의미합니다.

장군은 강습에 투입되는 모든 병사의 $a_i$ 값의 합을 최대화하고자 합니다. 하지만 한 가지 문제가 있습니다. 정렬된 병사 중 앞부분의 일부를 인토치아 전선으로 보내야 할 수도 있고, 뒷부분의 일부를 롱롱토치아에서의 첩보 작전에 투입해야 할 수도 있습니다. 이 경우 장군은 위치 번호가 구간 $[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$번째 시나리오에서 비토치아로 투입되는 병사들의 $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, 2, 3]$과 $[5, 6, 7]$을 차지하는 병사들로 구성된 두 부대를 강습에 투입해야 합니다.

두 번째와 여섯 번째 시나리오에서는 위치 $[3, 4, 5]$를 차지하는 병사들로 구성된 부대 하나만 만드는 것이 최적입니다.

세 번째와 네 번째 시나리오에서는 장군이 어떤 부대도 만들지 않고 공격 계획을 차분히 다시 생각해야 합니다.

일곱 번째 시나리오에서 장군은 위치 $[1, 2, 3]$과 $[4, 5, 6]$을 차지하는 병사들로 구성된 두 부대를 만들어야 합니다.

서브태스크

일부 테스트 그룹에서는 $k \le 30$을 만족합니다.