Farmer Johns $N$ Kühe ($1 \le N \le 50,000$) stehen täglich gleich zum Melken. Eines Tages organisiert er Ultimate Frisbee mit einigen. Einfachheitshalber wählt er einen zusammenhängenden Bereich, aber für Spaß aller soll Größe nicht zu stark differieren.

$Q$ ($1 \le Q \le 200,000$) mögliche Gruppen und Höhen ($1 \le height \le 1,000,000$): bestimme jeweils höchste minus niedrigste.

Eingabe

Lies von Standardeingabe.

Zeile 1: ganze $N$, $Q$ mit Leerzeichen.

Zeilen $2..N+1$: Zeile $i+1$, ganzzahlige Höhe von Kuh $i$.

Zeilen $N+2$..$N+Q+1$: ganze $A$, $B$ ($1 \le A \le B \le N$), Bereich $A$ bis $B$ inklusive.

Ausgabe

Schreibe auf Standardausgabe.

Zeilen $1..Q$: je eine Ganzzahl als Antwort, Differenz höchster und niedrigster Höhe im Bereich.

Beispiele

Eingabe 1

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

Ausgabe 1

6
3
0

Quelle: USACO Januar 2007, Silber