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

Рудольф подготовил набор из $$$n$$$ задач со сложностями $$$a_1 < a_2 < a_3 < \dots < a_n$$$. Он не совсем доволен балансом, поэтому хочет добавить не больше одной задачи, чтобы его исправить.

Для этого Рудольф придумал $$$m$$$ моделей задач и $$$k$$$ функций. Сложность $$$i$$$-й модели равна $$$d_i$$$, а сложность $$$j$$$-й функции равна $$$f_j$$$. Чтобы составить задачу, он выбирает значения $$$i$$$ и $$$j$$$ ($$$1 \le i \le m$$$, $$$1 \le j \le k$$$) и, совмещая $$$i$$$-ю модель с $$$j$$$-й функцией, получает новую задачу сложности $$$d_i + f_j$$$ (в массив $$$a$$$ добавляется новый элемент).

Чтобы определить дисбаланс набора, Рудольф сортирует сложности задач по возрастанию и находит самое большое значение $$$a_i - a_{i - 1}$$$ ($$$i > 1$$$).

Какого минимального значения дисбаланса может добиться Рудольф, добавив не больше одной задачи, составленной по описанным правилам?

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

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

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

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, a_3, \dots a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^9$$$, $$$a_i < a_{i+1}$$$) — сложности готовых задач.

Третья строка каждого набора содержит $$$m$$$ целых чисел $$$d_1, d_2, d_3, \dots d_m$$$ ($$$1 \le d_i \le 10^9$$$) — сложности моделей.

Четвёртая строка каждого набора содержит $$$k$$$ целых чисел $$$f_1, f_2, f_3, \dots f_k$$$ ($$$1 \le f_i \le 10^9$$$) — сложности функций.

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

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

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

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

Для каждого набора входных данных выведите единственное число — минимальный дисбаланс, которого сможет добиться Рудольф.

Пример
Входные данные
7
5 5 5
5 10 15 20 26
11 14 16 13 8
16 4 5 3 1
7 6 5
1 4 7 10 18 21 22
2 3 5 7 4 2
6 8 9 3 2
7 6 5
1 4 7 10 18 21 22
2 3 5 7 4 2
6 8 13 3 2
5 6 3
2 10 13 20 25
11 6 10 16 14 5
6 17 15
4 2 2
11 12 14 15
19 14
10 6
8 4 2
3 10 16 18 21 22 29 30
9 13 16 15
4 2
2 4 7
4 21
4 15 14 5
20 1 15 1 12 5 11
Выходные данные
5
4
5
8
2
7
11