Поиск подкастов
После того как Анна поиграла с парами
(guest, views) подкастов Лекса Фридмана, она потеряла информацию о гостях из некоторых пар и сохранила только views для этих подкастов. Анна просит вас помочь ей восстановить недостающие сведения о гостях. К тому же, есть ещё одна проблема в её списке. Она записала количество просмотров месяц назад, а у вас есть более свежие данные. Значит, в её списке цифры могут быть ниже, чем в ваших записях. Тем не менее, вы решаете дать лучший возможный ответ на каждый вопрос Анны.Входные данные
Первая строка входных данных содержит одно целое число
n (1 ≤ n ≤ ) — количество подкастов, сохранённых у вас в виде пар.Следующие
2n строк содержат пары: сначала имя гостя, а затем число views, которое набрал соответствующий подкаст. Список гостей упорядочен по возрастанию views.Затем идёт строка с одним целым числом
q (1 ≤ q ≤ n) — количество подкастов, которые Анна недавно потеряла.Следующая строка содержит
q целых чисел, разделённых пробелами, — количество просмотров для каждого подкаста из списка Анны.Выходные данные
Для каждого из
q вопросов программа должна вывести имя гостя того подкаста, у которого число views больше или равно данному числу. Если таких подкастов несколько, выводится имя того гостя, у кого views было наименьшим среди подходящих вариантов.Примеры
Ввод | Вывод |
5
Mark Zuckerberg
3800000
Kanye West
4000000
Vitalik Buterin
4500000
Joe Rogan
6200000
Elon Musk
6400000
3
6300000
3800000
6100000 | Elon Musk
Mark Zuckerberg
Joe Rogan |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 25 MB