Masz możliwość tworzenia robotów o wysokości należącej do przedziału $[0, d]$. Aby je przetestować, zbudowałeś tor o długości $n$ zawierający pewne przeszkody. Opis przeszkód jest podany jako tablica $a$. Jeśli $a_i = 0$, to na $i$-tej pozycji nie ma przeszkody, a w przeciwnym razie znajduje się tam przeszkoda o wysokości $a_i > 0$.
Aby przetestować robota, wybierasz przedział $[l, r]$ i przeprowadzasz go przez wszystkie przeszkody zawarte w tym przedziale. Gdy robot napotyka przeszkodę o wartości $a_i > 0$, zachodzi jedna z dwóch możliwości:
- Jeśli aktualna wysokość robota $h$ jest mniejsza niż $a_i$, to nic się nie dzieje, ponieważ robot jest zbyt niski, aby dosięgnąć przeszkody.
- Jeśli aktualna wysokość robota $h$ wynosi co najmniej $a_i$, to nowa wysokość zmienia się na $h' = h - a_i$.
Teraz musisz odpowiedzieć na $q$ zapytań. Dla każdego z $q$ przedziałów $[l_i, r_i]$ musisz podać maksymalną możliwą wysokość, z jaką robot może zakończyć bieg po pokonaniu przeszkód w tym przedziale, jeśli wysokość początkowa została wybrana z przedziału $[0, d]$.
Wejście
Pierwszy wiersz zawiera liczby całkowite $n, q, d$ ($1 \le n, q \le 3 \cdot 10^5, 1 \le d \le 10^9$) — długość tablicy oraz liczbę zapytań.
Drugi wiersz zawiera $n$ liczb całkowitych $a_i$ ($0 \le a_i \le 10^9$) — opis tablicy.
Kolejne $q$ wierszy zawiera pary liczb całkowitych $[l_i, r_i]$ ($1 \le l_i \le r_i \le n$) — opis zapytań.
Wyjście
Wypisz $q$ liczb całkowitych — odpowiedzi na zapytania.
Przykład
Wejście 1
5 3 5 0 2 6 1 3 5 5 1 5 1 3
Wyjście 1
2 2 3
Wejście 2
7 5 10 7 6 2 5 0 1 4 1 3 1 7 4 7 2 5 4 6
Wyjście 2
3 2 3 3 4