Байтоция планирует снова атаковать Битоцию! Десант на территорию противника — задача для настоящих смельчаков, поэтому в нем примут участие солдаты лучшего байтоцкого спецподразделения — «Байтогрома».

На инструктаже у генерала Байтчака собралось $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$-й из них должно находиться одно целое число, обозначающее максимальную сумму значений $a_i$ солдат, отправленных в Битоцию в $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$.