你有能力製造高度在 $[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