E. Сервал и модуль
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$, состоящий из $$$n$$$ целых неотрицательных чисел, и магическое число $$$k$$$ ($$$k\ge 1$$$, $$$k$$$ — целое число). Сервал построил другой массив $$$b$$$ длины $$$n$$$, где $$$b_i = a_i \bmod k$$$ выполняется$$$^{\text{∗}}$$$ для всех $$$1\leq i\leq n$$$. Затем он перемешал $$$b$$$.

Вам даны два массива $$$a$$$ и $$$b$$$. Найдите подходящее магическое число $$$k$$$. Однако существует небольшая вероятность, что Сервал вас обманул, и такого целого числа не существует. В этом случае выведите $$$-1$$$.

Можно показать, что при заданных ограничениях задачи, если такое целое число $$$k$$$ существует, то существует корректный ответ не больше $$$10^9$$$. Поэтому для вашего ответа должно выполняться $$$k\le 10^9$$$.

$$$^{\text{∗}}$$$$$$a_i \bmod k$$$ обозначает остаток от деления $$$a_i$$$ на $$$k$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i\leq 10^6$$$) — элементы массива $$$a$$$.

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0\leq b_i\leq 10^6$$$) — элементы массива $$$b$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^4$$$.

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

Для каждого набора входных данных выведите одно целое число $$$k$$$ ($$$1\leq k\leq 10^9$$$) — магическое число, которое вы нашли. Выведите $$$-1$$$, если такого числа не существует.

Если существует несколько ответов, вы можете вывести любой из них.

Пример
Входные данные
5
4
3 5 2 7
0 1 1 1
5
3 1 5 2 4
1 2 3 4 5
6
2 3 4 7 8 9
1 2 3 6 7 8
5
21 22 25 28 20
0 1 2 1 0
6
1 1 2 3 5 8
0 0 1 1 0 0
Выходные данные
2
31415926
-1
4
-1
Примечание

В первом наборе входных данных, если $$$k\ge 3$$$, то $$$2=a_3\bmod k$$$ должно быть в массиве $$$b$$$, что приводит к противоречию. Для $$$k = 1$$$, $$$[a_1\bmod k, a_2\bmod k, a_3\bmod k, a_4 \bmod k] = [0,0,0,0]$$$, что не является перестановкой $$$b$$$. Для $$$k = 2$$$, $$$[a_1\bmod k, a_2\bmod k, a_3\bmod k, a_4 \bmod k] = [1,1,0,1]$$$, что является перестановкой $$$b$$$. Таким образом, единственный возможный ответ: $$$k=2$$$.

Во втором наборе входных данных обратите внимание, что $$$b$$$ может быть получен путем перемешивания $$$a$$$. Таким образом, все целые числа от $$$6$$$ до $$$10^9$$$ являются возможными ответами.

В третьем наборе можно показать, что искомого $$$k$$$ не существует. Сервал вас обманул!