$N$ krów Farmer John ($1 \le N \le 50,000$) codziennie stoi tak samo do udoju. Organizuje z częścią ultimate frisbee. Dla prostoty wybiera spójny odcinek, ale dla zabawy wszystkich wzrost nie może bardzo się różnić.

$Q$ ($1 \le Q \le 200,000$) możliwych grup i wzrosty ($1 \le height \le 1,000,000$): znajdź różnicę najwyższej i najniższej w każdej.

Wejście

Czytaj ze standardowego wejścia.

Wiersz 1: całkowite $N$, $Q$ ze spacją.

Wiersze $2..N+1$: wiersz $i+1$, całkowity wzrost krowy $i$.

Wiersze $N+2$..$N+Q+1$: całkowite $A$, $B$ ($1 \le A \le B \le N$), zakres $A$ do $B$ włącznie.

Wyjście

Pisz na standardowe wyjście.

Wiersze $1..Q$: całkowite dla odpowiedzi, różnica najwyższej i najniższej w zakresie.

Przykład

Wejście 1

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

Wyjście 1

6
3
0

Źródło: USACO styczeń 2007, srebro