Podcast search
After playing with pairs
(guest, views) of Lex Fridman’s podcasts, Anna loses the guest information from some of the pairs and is left with only views for those podcasts. She wants you to help her restore that information. There is one more issue with her list as well. She wrote the information about the views a month ago, while yours is fresh. So, the views in her list might be lower than yours. But you decide to give your best guess for each of the questions Anna asks you.Input
The first line of the input contains a single integer
n (1 ≤ n ≤ ) - the number of podcasts you’ve kept as a list of pairs. The next
2n lines contain pairs of guests and views. First comes the name of the guest, then the number of views that the podcast obtained. The list of guests is ordered by views in increasing order.The following line contains a single integer
q (1 ≤ q ≤ n) - the number of podcasts Anna lost recently.The next
q lines contain integers representing the view counts of each podcast Anna lost in her list.Output
For each of the
q questions, the program should print the name of the podcast guest that got views greater or equal to the given number. If there are several such podcasts print the guest name that had the minimum number of viewsExamples
Input | Output |
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