You have an ability to create robots of height lying in $[0, d]$. To test them, you constructed a line of length $n$ containing some obstacles. The description of obstacles is given to you as an array $a$. If $a_i = 0$, then there is no obstacle at the $i$-th position, and otherwise, there is an obstacle of height $a_i > 0$.

To test your robot, you select a segment $[l, r]$ and run it through all obstacles contained in the segment. When the robot encounters an obstacle with value $a_i > 0$, one of the two possibilities happens:

• If the current height of the robot $h$ is smaller than $a_i$, then nothing happens since the robot is too short to reach the obstacle.
• If the current height of the robot $h$ is at least $a_i$, then the new height changes to $h' = h - a_i$.

Now you need to answer $q$ queries. For each of the $q$ segments $[l_i, r_i]$, you need to tell the maximum possible height with which the robot can end up after running through the obstacles in the segment if the initial height was picked from the interval $[0, d]$.

Input

First line contains a pair of integers $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$) — length of the array and number of queries.

Second line contains $n$ integers $a_i$ ($0 \le a_i \le 10^9$) — description of the array.

Next $q$ lines contain a pair of integers $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$) — description of the queries.

Output

Output $q$ integers — answers to the queries.

Examples

Input 1

5 3 5
0 2 6 1 3
5 5
1 5
1 3

Output 1

2
2
3

Input 2

7 5 10
7 6 2 5 0 1 4
1 3
1 7
4 7
2 5
4 6

Output 2

3
2
3
3
4