$N$ פרות Farmer John ($1 \le N \le 50,000$) עומדות מדי יום לחליבה באותו סדר. יום אחד מארגן אולטימייט פריסבי עם חלקן. לפשטות בוחר קטע רצוף, אך להנאת כולן הגבהים לא שונים מדי.

$Q$ ($1 \le Q \le 200,000$) קבוצות אפשריות וגבהים ($1 \le height \le 1,000,000$): מצאו בכל אחת הפרש הגבוהה והנמוכה.

קלט

קראו מהקלט הסטנדרטי.

שורה 1: שלמים $N$, $Q$ ברווח.

שורות $2..N+1$: שורה $i+1$, גובה שלם של פרה $i$.

שורות $N+2$..$N+Q+1$: שלמים $A$, $B$ ($1 \le A \le B \le N$), טווח $A$ עד $B$ כולל.

פלט

כתבו לפלט הסטנדרטי.

שורות $1..Q$: שלם לכל תשובה, הפרש הגבוהה והנמוכה בטווח.

דוגמאות

קלט 1

6 3
1
7
3
4
2
5
1 5
4 6
2 2

פלט 1

6
3
0

מקור: USACO ינואר 2007, כסף