E. Онлайн-курс по физкультуре
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У студентов одного неизвестного ПТУ нет обязательных занятий по физкультуре. Чтобы исправить это недоразумение, $$$q$$$ студентов решили самостоятельно записаться в спортзал. В спортзале действует система абонементов на посещения, в $$$i$$$-й из $$$n$$$ дней известна цена покупки абонемента $$$a_i$$$. Разрешается покупать более одного абонемента за день.

Купленный в день $$$i$$$ абонемент можно активировать как день $$$i$$$, так и в любой день позднее. Каждый из абонементов после активации будет действовать $$$k$$$ дней, то есть активированный в день $$$t$$$ абонемент будет действовать в дни с номерами $$$t, t + 1, \dots, t + k - 1$$$.

Известно, что $$$j$$$-й студент хочет посещать спортзал каждый день со дня $$$l_j$$$ по день $$$r_j$$$ включительно. Алгоритм похода в спортзал в некоторый день $$$i$$$ ($$$l_j \le i \le r_j$$$) любого из студентов выглядит следующим образом:

  1. Студент подходит к кассе перед спортзалом и покупает несколько абонементов по цене $$$a_i$$$ за штуку (возможно, не покупает ни одного).
  2. Если у студента есть хотя бы один действующий сегодня абонемент, то он просто проходит в спортзал. Иначе, он активирует один из купленных сегодня или ранее абонементов, и проходит в спортзал.

Заметим, что ни один студент не придет в спортзал раньше дня $$$l_j$$$, а потому каждый студент обязательно купит не менее одного абонемента в день $$$l_j$$$.

Помогите каждому студенту посчитать, какую минимальную сумму ему придется потратить, чтобы посещать зал в свои дни.

Входные данные

В первой строке заданы три целых числа $$$n$$$, $$$q$$$ и $$$k$$$ ($$$1 \le n, q \le 300\,000$$$; $$$1 \le k \le n$$$) — количество дней, количество студентов и длительность любого абонемента.

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — стоимость одного абонемента в соответствующий день.

В следующих $$$q$$$ строках заданы два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — отрезок дней, в которые соответствующий студент хочет посещать спортзал.

Выходные данные

Для каждого студента выведите минимальную сумму, необходимую ему для посещения спортзала в выбранный отрезок дней.

Пример
Входные данные
7 5 2
2 15 6 3 7 5 6
1 2
3 7
5 5
7 7
3 5
Выходные данные
2
12
7
6
9
Примечание

Рассмотрим как нужно покупать абонементы каждому из студентов:

  • Первому студенту достаточно купить один сертификат в день $$$1$$$.
  • Второму студенту нужно купить один сертификат в день $$$3$$$ и два сертификата в день $$$4$$$. Обратите внимание, что он не обязан использовать их в тот же день.
  • Третьему студенту достаточно купить один сертификат в день $$$5$$$.
  • Четвертому студенту достаточно купить сертификат в день $$$7$$$.
  • Пятому студенту нужно купить по одному сертификату в дни $$$3$$$ и $$$4$$$.