강습 2

바이토시아가 비토시아를 다시 공격하려고 한다. 적진에 낙하하는 작전은 진정한 강골의 몫이라, 이번에는 바이토시아 최정예 특수부대 바이토그롬의 병사들이 투입된다.

바이토착 장군의 사열에 병사 $n$명이 모였다. 병사들은 왼쪽에서 오른쪽으로 $1$번부터 $n$번까지 번호가 붙은 한 줄로 섰다. 장군은 비토시아로 보낼 부대를 몇 개 고르려 한다. 각 부대는 연속된 위치를 차지하는 정확히 $k$명의 병사로 이루어져야 한다. 병사는 최대 한 부대에만 속할 수 있다. 장군은 부대 개수에 제약이 없으며, 부대를 하나도 만들지 않고 공격을 잠시 미뤄도 된다.

각 병사의 능력은 정수 $a_i$로 나타낸다. $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, \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]$ 구간에 속한 병사만 보낼 수 있다.

$q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 시나리오에서 비토시아로 보내는 병사들의 $a_i$ 합의 최댓값을 쓴다.

첫 번째와 다섯 번째 시나리오에서는 위치 $[1, 2, 3]$과 $[5, 6, 7]$의 병사로 부대 두 개를 만드는 것이 최적이다. 두 번째와 여섯 번째 시나리오에서는 위치 $[3, 4, 5]$의 병사로 부대 하나만 만드는 것이 최적이다. 세 번째와 네 번째 시나리오에서 장군은 부대를 만들지 않고 작전을 차분히 다시 검토한다. 일곱 번째 시나리오에서는 위치 $[1, 2, 3]$과 $[4, 5, 6]$의 병사로 부대 두 개를 만든다.