你有能力制造高度在 $[0, d]$ 范围内的机器人。为了测试它们，你建造了一条长度为 $n$ 且包含一些障碍物的跑道。障碍物的描述由数组 $a$ 给出。如果 $a_i = 0$，则第 $i$ 个位置没有障碍物；否则，该位置有一个高度为 $a_i > 0$ 的障碍物。

为了测试你的机器人，你选择一个区间 $[l, r]$ 并让机器人通过该区间内的所有障碍物。当机器人遇到高度为 $a_i > 0$ 的障碍物时，会发生以下两种情况之一：

• 如果机器人当前的高度 $h$ 小于 $a_i$，则什么也不会发生，因为机器人太矮了，够不到该障碍物。
• 如果机器人当前的高度 $h$ 至少为 $a_i$，则其高度将变为 $h' = h - a_i$。

现在你需要回答 $q$ 个询问。对于这 $q$ 个区间 $[l_i, r_i]$ 中的每一个，你需要求出：如果机器人的初始高度是从区间 $[0, d]$ 中任意选择的，那么在通过该区间内的所有障碍物后，机器人可能达到的最大最终高度。

输入格式

第一行包含三个整数 $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$) —— 数组的长度和询问的数量。

第二行包含 $n$ 个整数 $a_i$ ($0 \le a_i \le 10^9$) —— 数组的描述。

接下来的 $q$ 行，每行包含两个整数 $l_i, r_i$ ($1 \le l_i \le r_i \le n$) —— 询问的区间。

输出格式

输出 $q$ 个整数 —— 对应询问的答案。

样例

输入样例 1

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

输出样例 1

2
2
3

输入样例 2

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

输出样例 2

3
2
3
3
4