あなたは高さが $[0, d]$ の範囲にあるロボットを作ることができます。それらをテストするために、いくつかの障害物を含む長さ $n$ の直線コースを作りました。障害物の情報は配列 $a$ として与えられます。$a_i = 0$ のとき $i$ 番目の位置に障害物はなく、そうでないとき高さ $a_i > 0$ の障害物があります。
ロボットをテストする際、区間 $[l, r]$ を選び、その区間に含まれるすべての障害物を順番に通過させます。ロボットが値 $a_i > 0$ の障害物に遭遇したとき、次の 2 つのうちいずれかが起こります:
- ロボットの現在の高さ $h$ が $a_i$ より小さい場合、ロボットは低すぎて障害物に届かないため、何も起こりません。
- ロボットの現在の高さ $h$ が $a_i$ 以上である場合、新しい高さは $h' = h - a_i$ に変化します。
いま、$q$ 個のクエリに答える必要があります。$q$ 個の区間 $[l_i, r_i]$ のそれぞれについて、初期の高さを区間 $[0, d]$ から選んだとき、区間内の障害物を通過した後にロボットが最終的に持ちうる最大の可能な高さを求めてください。
入力
1 行目には整数 $n, q, d$($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$)が与えられます。これらは配列の長さとクエリの数です。
2 行目には $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