Taco Book Recommendations

In this problem, you are given several test cases. For each test case, you are provided a list of favorite book genres and a list of available books. Each book is represented by a unique identifier (book ID) and its genre. Your task is to select one book for each favorite genre such that the selected book has the minimum book ID among all books of that genre. If there is no available book for a given genre, output -1 for that genre.

Formally, for a favorite genre g, you need to compute [ book_{min} = \min{ id : (id, genre) \text{ is given and } genre = g } ] If no such book exists, output -1.

The input consists of T test cases. For each test case, the first line contains an integer G denoting the number of favorite genres, followed by a line containing G space‐separated genre names. The next line contains an integer B denoting the number of available books, followed by B lines each containing a book description in the format: book_id and genre.

Your program should output one line per test case, where the line contains the recommended book IDs for each favorite genre in the order given, separated by a space. The input is read from standard input (stdin) and the output is written to standard output (stdout).

inputFormat

The input is given as follows:

The first line contains an integer T, the number of test cases. For each test case:

1. A line containing an integer G, the number of favorite genres.
2. A line containing G space-separated strings representing the favorite genres.
3. A line containing an integer B, the number of available books.
4. B lines, each containing two entries: a book ID (integer) and a genre (string).

Example:

2 3 mystery romance fantasy 4 100 mystery 101 romance 102 fantasy 103 mystery 2 sci-fi fantasy 3 104 sci-fi 105 drama 106 fantasy

outputFormat

For each test case, output a single line containing the chosen book IDs for the favorite genres, separated by a single space. If for a given favorite genre no available book exists, output -1 instead.

Example Output:

100 101 102 104 106## sample

2
3
mystery romance fantasy
4
100 mystery
101 romance
102 fantasy
103 mystery
2
sci-fi fantasy
3
104 sci-fi
105 drama
106 fantasy

100 101 102
104 106