Одна из самых сложных и важных задач Деда Мороза в новогоднюю ночь — составление маршрута перемещения по городам России. Для этого он заранее измеряет расстояния от его усадьбы до каждого города (по прямой). Далее дедушка руководствуется следующим правилом. Пусть очередным пунктом маршрута является город, расстояние до которого от усадьбы равно \(x_i\) км. Тогда следующим пунктом маршрута станет город, находящийся от усадьбы на расстоянии \(x_j\) км, где значение \(\left|x_i-x_j\right|\) наименьшее. Если таких городов несколько, то будет выбран первый из них по алфавиту.
Напишите программу, определяющую по информации о городах, требующих посещения, и текущем городе следующий город маршрута.
Формат ввода
В первой строке вводится одно натуральное число \(n\) — количество ещё не посещённых городов (\(1\leqslant n\leqslant 10^6\)).
Далее в \(n\) строках вводятся названия этих городов и расстояния от них до усадьбы Деда Мороза (расстояния целые, положительные, не превосходят \(10^9\)). Гарантируется, что названия всех городов различны. Название города состоит строго только из латинских букв (все буквы строчные, кроме первой — она заглавная).
В следующей строке вводится натуральное число \(k\) — количество рассматриваемых случаев текущего местоположения Деда Мороза (\(1\leqslant k\leqslant 10^5\)).
В последней строке через пробел вводится \(k\) натуральных чисел, не превосходящих \(10^9\), — расстояния от усадьбы до возможных текущих городов.
Формат вывода
Для каждого возможного варианта текущего положения Деда Мороза выведите в отдельной строке название следующего города на маршруте новогоднего волшебника.
Запрещенные операторы: search; find
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
Moscow 3152
Petersburg 2718
Sochi 5011
3
3307 2599 6306
|
Moscow
Petersburg
Sochi
|