Anda memiliki kemampuan untuk membuat robot dengan tinggi yang berada pada $[0, d]$. Untuk mengujinya, Anda membangun sebuah lintasan sepanjang $n$ yang berisi beberapa rintangan. Deskripsi rintangan diberikan kepada Anda sebagai sebuah larik $a$. Jika $a_i = 0$, maka tidak ada rintangan pada posisi ke-$i$, dan sebaliknya, terdapat rintangan dengan tinggi $a_i > 0$.
Untuk menguji robot Anda, Anda memilih sebuah segmen $[l, r]$ dan menjalankannya melewati semua rintangan yang berada di dalam segmen tersebut. Ketika robot menemui rintangan dengan nilai $a_i > 0$, salah satu dari dua kemungkinan berikut terjadi:
- Jika tinggi robot saat ini $h$ lebih kecil dari $a_i$, maka tidak terjadi apa-apa karena robot terlalu pendek untuk mencapai rintangan tersebut.
- Jika tinggi robot saat ini $h$ setidaknya $a_i$, maka tinggi barunya berubah menjadi $h' = h - a_i$.
Sekarang Anda perlu menjawab $q$ kueri. Untuk masing-masing dari $q$ segmen $[l_i, r_i]$, Anda perlu menentukan tinggi maksimum yang mungkin dimiliki robot pada akhir perjalanan setelah melewati rintangan di segmen tersebut jika tinggi awalnya dipilih dari interval $[0, d]$.
Masukan
Baris pertama berisi bilangan bulat $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$) — panjang larik dan jumlah kueri.
Baris kedua berisi $n$ bilangan bulat $a_i$ ($0 \le a_i \le 10^9$) — deskripsi larik.
$q$ baris berikutnya berisi sepasang bilangan bulat $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$) — deskripsi kueri.
Keluaran
Keluarkan $q$ bilangan bulat — jawaban untuk kueri tersebut.
Contoh
Masukan 1
5 3 5 0 2 6 1 3 5 5 1 5 1 3
Keluaran 1
2 2 3
Masukan 2
7 5 10 7 6 2 5 0 1 4 1 3 1 7 4 7 2 5 4 6
Keluaran 2
3 2 3 3 4