Nauuo — девочка, которая любит программировать.
Однажды она решала задачу, в которой нужно было посчитать сумму некоторых чисел по модулю \(p\).
Она написала следующий код и получила вердикт «Неправильный ответ».
Вскоре она нашла свою ошибку: функция ModAdd работает только для чисел в полуинтервале \([0,p)\), но числа в этой задаче могут быть вне этого диапазона. Она заинтересовалась неправильной функцией и захотела узнать результат ее выполнения.
К сожалению исходный код работает слишком долго, так что она попросила вас помочь.
Вам дан массив целых чисел \(a_1,a_2,\ldots,a_n\) и число \(p\), Nauuo сделает \(m\) запросов. В каждом запросе вам даны \(l\) и \(r\), вам нужно посчитать результат выполнения Sum(a,l,r,p). Вы можете посмотреть определение функции Sum в данном псевдокоде.
Обратите внимания, что числа в данном коде не переполняются.