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