Nauuo is a girl who loves programming. One day, she was working on a problem that required calculating the sum of some numbers modulo $p$.

She wrote the following code and received a WA (Wrong Answer) verdict.

She quickly discovered the bug—the ModAdd function only works correctly for numbers in the range $[0, p)$, but the numbers in this problem might fall outside this range. She is curious about the result of this incorrect function, so she wants to know its output.

However, the original code runs too slowly, so she has come to you for help.

Given an array $a_1, a_2, \dots, a_n$ and a number $p$, there are $m$ queries. Each query provides two numbers $l$ and $r$, and you need to calculate the return value of the function Sum(a, l, r, p). The definition of the Sum function is provided in the pseudocode above.

Note that in the code above, integers will not overflow.

Input

The first line contains three integers $n$, $m$, and $p$, representing the length of the array, the number of queries, and the modulus, respectively. Note that the modulus is only used in ModAdd.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$, representing the given array.

The next $m$ lines each contain two integers $l$ and $r$, for which you need to calculate Sum(a, l, r, p).

Output

Output $m$ integers in order, one per line, representing the answers to the queries.

Examples

Input 1

4 5 6
7 2 -3 17
2 3
1 3
1 2
2 4
4 4

Output 1

-1
0
3
10
11

Note

Idea: rushcheyo, Solution: ccz181078, Code: rushcheyo & ccz181078, Data: rushcheyo

For $100\%$ of the data, $1 \le n \le 10^6$, $1 \le m \le 2 \times 10^5$, $1 \le p \le 10^9$, $-10^9 \le a_i \le 10^9$, $1 \le l \le r \le n$.