יש לך יכולת ליצור רובוטים שגובהם נמצא בקטע $[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