E. Укомплектование шахматной команды
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп готовит команду к предстоящей игре на шахматном турнире. Полная команда для турнира должна состоять из $$$n+1$$$ участника.

В его команде $$$n$$$ участников, у $$$i$$$-го уровень подготовки равен $$$a_i$$$. Поликарпу предстоит выбрать последнего участника команды.

В команде соперника $$$n+1$$$ участник, у $$$j$$$-го уровень подготовки равен $$$b_j$$$.

У Поликарпа есть $$$m$$$ вариантов выбора последнего участника. У $$$k$$$-го из них уровень подготовки равен $$$c_k$$$.

До начала игры Поликарп ставит каждого игрока своей команды в пару с игроком команды соперника. Каждый игрок обеих команд состоит ровно в одной паре. Сложность игры для конкретного игрока — это разница между уровнем подготовки его соперника и его уровнем. То есть, если $$$i$$$-й игрок команды Поликарпа в паре с $$$j$$$-м игроком команды соперника, то сложность равна $$$b_j - a_i$$$. Сложность игры для команды — это максимум по сложностям ее участников.

Поэтому перед началом игры Поликарп хочет поставить всех игроков в пары так, чтобы сложность игры для его команды была как можно меньше.

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

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

В первой строке записано одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество игроков в команде Поликарпа.

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ — уровень подготовки $$$i$$$-го игрока команды Поликарпа.

В третьей строке записано $$$n+1$$$ целое число $$$b_1, b_2, \dots, b_{n+1}$$$ ($$$1 \le b_j \le 10^9$$$), где $$$b_j$$$ — уровень подготовки $$$j$$$-го игрока команды соперника.

В четвертой строке записано одно целое число $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — количество вариантов последнего игрока.

В пятой строке записаны $$$m$$$ целых чисел $$$c_1, c_2, \dots, c_m$$$ ($$$1 \le c_k \le 10^9$$$), где $$$c_k$$$ — уровень подготовки $$$k$$$-го игрока среди вариантов для последнего участника команды Поликарпа.

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

Выведите $$$m$$$ целых чисел — $$$k$$$-е должно быть равно минимальной сложности игры, которую может получить Поликарп, если он выберет $$$k$$$-й вариант последнего игрока.

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

В первом примере лучшие пары для первых трех вариантов выглядят следующим образом. Обратите внимание, что может существовать несколько корректных пар, которые дают наименьший ответ.

Первый вариант:

Команда Поликарпа: 6 1 3 1 10 4

Команда соперника: 9 4 2 5  9 8

Соответствующие сложности игры для каждого игрока равны: 3, 3, -1, 4, -1, 4. Максимум равен 4, поэтому он является сложностью игры для команды.

Второй вариант:

Команда Поликарпа: 10 4 1 3 7 6

Команда соперника:  9 4 2 5 9 8

Третий вариант:

Команда Поликарпа: 6 3 1 4 10 6

Команда соперника: 9 4 2 5  9 8