Problem D
Drink Menu
To widen their mixological horizons, some of your bar’s patrons have decided to work themselves through the entire drink menu, top to bottom, over a period of many visits. Due to their forgetfulness, decreptitude, or levels of inebriation, these patrons cannot be trusted with keeping track of how far they’ve progressed down the menu.
Thus, you decide to take responsibility for always serving the right drink to the right customer, so that each customer goes through the menu in order from top to bottom, no matter in which order the customers arrive.
Input
The first line contains the number $n$ of drinks and the number $m$ of orders, where $1\leq n\leq 1\, 000$ and $1\leq m\leq 10\, 000$.
The next $n$ lines each contain the name of a drink, in the order of the drink menu. The following $m$ lines each contain the name of a customer ordering a drink. Both drink and customer names consist of alphabetic characters from A-Z, a–z, and space; each name is at most $25$ characters long and neither starts nor ends with space. The drinks and the customers have unique names. There are at most $1\, 000$ different customers. It is guaranteed that no customer orders more than $n$ drinks.
Output
Exactly $m$ lines containing the drinks you serve in the proper order.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 3 Old Fashioned Aperol Spritz Thore Oskar Thore |
Old Fashioned Old Fashioned Aperol Spritz |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 3 Old Fashioned Aperol Spritz Thore Thore Oskar |
Old Fashioned Aperol Spritz Old Fashioned |
