Остаток суммы отрезка

Даны список из $n$ чисел, число $m$ и $q$ запросов.

Для каждого запроса выведите остаток от деления суммы элементов с $l$-го по $r$-й на $m$. Остаток берётся неотрицательный, как это делает Python.

В первой строке числа $n$ от $1$ до $2 \cdot 10^5$, $q$ от $1$ до $10^5$ и $m$ от $1$ до $10^9$. Во второй — $n$ целых чисел от $-10^9$ до $10^9$. В следующих $q$ строках — по два числа $l$ и $r$.

Числа через пробел.