Сізде биіктігі $[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