F. Максимальное модульное равенство
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ длины $$$n$$$ и $$$q$$$ запросов вида $$$l$$$, $$$r$$$.

Для каждого запроса найдите такое максимальное $$$m$$$, что все числа $$$a_l$$$, $$$a_{l+1}$$$, ..., $$$a_r$$$ равны по модулю $$$m$$$. Иными словами, $$$a_l \bmod m = a_{l+1} \bmod m = \dots = a_r \bmod m$$$, где $$$a \bmod b$$$ — это остаток от деления $$$a$$$ на $$$b$$$. В частности, если число $$$m$$$ может быть бесконечно большим, выведите $$$0$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$, $$$q$$$ ($$$1 \le n, q \le 2\cdot 10^5$$$) — длину массива и количество запросов.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива.

В следующих $$$q$$$ строках каждого набора вводится по два числа $$$l$$$, $$$r$$$ ($$$1 \le l \le r \le n$$$) — отрезок запроса.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$, как и сумма $$$q$$$ не превосходит $$$2\cdot 10^5$$$.

Выходные данные

Для каждого запроса выведите максимальное значение $$$m$$$, описанное в условии.

Пример
Входные данные
3
5 5
5 14 2 6 3
4 5
1 4
2 4
3 5
1 1
1 1
7
1 1
3 2
1 7 8
2 3
1 2
Выходные данные
3 1 4 1 0 
0 
1 6
Примечание

В первом запросе первого примера $$$6 \bmod 3 = 3 \bmod 3 = 0$$$, можно показать, что для больших $$$m$$$ нужное условие выполняться не будет.

В третьем запросе первого примера $$$14 \bmod 4 = 2 \bmod 4 = 6 \bmod 4 = 2$$$, можно показать, что для больших $$$m$$$ нужное условие выполняться не будет.