| Codeforces Round 564 (Div. 1) |
|---|
| Закончено |
Nauuo — девочка, которая любит программировать.
Однажды она решала задачу, в которой нужно было посчитать сумму некоторых чисел по модулю $$$p$$$.
Она написала следующий код и получила вердикт «Неправильный ответ».
Вскоре она нашла свою ошибку: функция ModAdd работает только для чисел в полуинтервале $$$[0,p)$$$, но числа в этой задаче могут быть вне этого диапазона. Она заинтересовалась неправильной функцией и захотела узнать результат ее выполнения.
К сожалению исходный код работает слишком долго, так что она попросила вас помочь.
Вам дан массив целых чисел $$$a_1,a_2,\ldots,a_n$$$ и число $$$p$$$, Nauuo сделает $$$m$$$ запросов. В каждом запросе вам даны $$$l$$$ и $$$r$$$, вам нужно посчитать результат выполнения Sum(a,l,r,p). Вы можете посмотреть определение функции Sum в данном псевдокоде.
Обратите внимания, что числа в данном коде не переполняются.
В первой строке записаны три целых числа $$$n$$$, $$$m$$$, $$$p$$$ ($$$1 \le n \le 10^6$$$, $$$1 \le m \le 2 \cdot 10^5$$$, $$$1 \le p \le 10^9$$$) — длина данного массива, количество запросов и модуль. Обратите внимание, что модуль используется только в функции ModAdd.
Во второй строке записаны $$$n$$$ целых чисел $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9\le a_i\le10^9$$$) — данный массив.
В каждой из следующих $$$m$$$ строк записаны два целых числа $$$l$$$, $$$r$$$ ($$$1\le l\le r\le n$$$) — вам нужно посчитать значение функции Sum(a,l,r,p).
Выведите $$$m$$$ целы чисел, ответов на запросы в данном порядке.
4 5 6 7 2 -3 17 2 3 1 3 1 2 2 4 4 4
-1 0 3 10 11
