| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 77 | 7 | 5 | 10.000% |
A hotel booking website would like to add search suggestion feature on their website. This suggestion will be used to help customers searching for hotels in a particular city. Typically, users would type a prefix of a city name and the search would suggest the three most popular city names that match with that prefix. Since this website needs to process millions of search queries per day, a limit has been placed to reduce the server workload. The search suggestion feature will be activated only if the search query matches no greater than one thousand city names. Your assignment is to create the search suggestion feature for this booking website.
The first part of the input is city data. The first line is the number of cities (N where 1 ≤ N ≤ 500,000) following by pairs of data consisting of city name and its popularity score (S where 1 ≤ S ≤ 100), which is separated by a comma (“,”). The city data is sorted in ascending order by city name. The second part of the input is query data. Similarly, the first line is the number of queries (Q where 1 ≤ Q ≤ 300,000) following by a list of queries which is a string.
For each query, output the query and its corresponding search suggestions. The query could result in 3 types of result, which are:
In case that the popularity score of cities that match with the query are equal, the result must shows in the ascending order of city name.
7 BANGKOK,71 BEIJING,72 LOMBARDY,65 LONDON,78 LOS ANGELES,80 LOUVRE,65 ZURICH,70 4 Ban London Lo y
Ban BANGKOK,71 London LONDON,78 Lo LOS ANGELES,80 LONDON,78 LOMBARDY,65 y N/A
Please note that the system is case-insensitive.