CF1172F.Nauuo and Bug

Nauuo is a girl who loves coding.

One day she was solving a problem which requires to calculate a sum of some numbers modulo $p$.

She wrote the following code and got the verdict "Wrong answer".

She soon discovered the bug — the ModAdd function only worked for numbers in the range $[0,p)$, but the numbers in the problem may be out of the range. She was curious about the wrong function, so she wanted to know the result of it.

However, the original code worked too slow, so she asked you to help her.

You are given an array $a_1,a_2,\ldots,a_n$ and a number $p$. Nauuo will make $m$ queries, in each query, you are given $l$ and $r$, and you have to calculate the results of Sum(a,l,r,p). You can see the definition of the Sum function in the pseudocode above.

Note that the integers won't overflow in the code above.

Nauuo 是一位热爱编程的女孩。

某天，她正在解决一道需要计算若干数字对 $p$ 取模之和的问题。

她编写了如下代码，却得到了 “答案错误” 的判题结果。

她很快发现了错误——ModAdd 函数仅对位于区间 $[0,p)$ 内的数有效，但题目中的数字可能超出该范围。她对这个有误的函数产生了好奇，因此想了解它实际会返回什么结果。

然而，原始代码运行速度太慢，于是她请你帮忙。

你将得到一个数组 $a_1,a_2,\ldots,a_n$ 和一个数 $p$。Nauuo 将进行 $m$ 次查询；每次查询给出 $l$ 和 $r$，你需要计算 Sum(a,l,r,p) 的结果。Sum 函数的定义见上方伪代码。

注意：上述代码中整数不会发生溢出。

The first line contains three integers $n$, $m$, $p$ ($1 \le n \le 10^6$, $1 \le m \le 2 \cdot 10^5$, $1 \le p \le 10^9$) — the length of the given array, the number of queries and the modulus. Note that the modulus is used only in the ModAdd function.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-10^9\le a_i\le10^9$) — the given array.

In the following $m$ lines, each line contains two integers $l$, $r$ ($1\le l\le r\le n$) — you have to calculate the result of Sum(a,l,r,p).

第一行包含三个整数 $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) 的结果。

The output contains $m$ integers to answer the queries in the given order.

输出包含 $m$ 个整数，按给定顺序回答各个查询。