Олимпиадный тренинг

Задача . E. Укомплектование шахматной команды

Задача

Темы: *особая задача Бинарный поиск жадные алгоритмы Структуры данных

Поликарп готовит команду к предстоящей игре на шахматном турнире. Полная команда для турнира должна состоять из \(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\)-й вариант последнего игрока.

Примечание

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

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

Команда Поликарпа: 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