Problem S
Höfundaleit
Languages
en
is
Hallgerður Stuttbrók is stood in the library in Reyðarfjörður. She is looking for something fun to read, but cannot find the book she has in mind. This is because she does not remember the name of the author, and at this library the books are ordered by the names of the authors. Can you help her find where the books she wants to read are located?
Input
The first line contains two integers $n$, the number of books at the library, and $q$, the number of books Hallgerður wants to read. The next $n$ lines each contain the title and author name of one book, separated by a comma. Finally there are $q$ lines, each containing one book title, each giving the title of one book Hallgerður wants to read. The titles and author names will only contain English lower and upper case letters along with underscores. No two different books will have the same title. Each title and author name is at most $25$ letters. The total length of all strings in the input will be at most $10^6$ letters.
Output
For each book Hallgerður wants to read, print the location of the book in the order of all books at the library. We consider the first book to be number $1$, the second number $2$ and so on. If the book is not available at the library, print $-1$ instead. If an author has more than one book, the internal order of those books is determined by the title. The order is the usual alphabetical order of strings with respect to ASCII-values. Note that this is the same order as the built-in sorting functionality of most programming languages produces. For example sorted in Python or std::sort in C++.
Scoring
|
Group |
Points |
Constraints |
|
1 |
10 |
$0 \leq n, q \leq 100$, no requested books are available at the library. |
|
2 |
10 |
$0 \leq n, q \leq 100$, no author has more than one book, the library books are sorted by author, all books are available. |
|
3 |
20 |
$0 \leq n, q \leq 100$, no author has more than one book, all books are available. |
|
4 |
20 |
$0 \leq n, q \leq 100$, no author has more than one book. |
|
5 |
20 |
$0 \leq n, q \leq 100$. |
|
6 |
20 |
$0 \leq n, q \leq 100\, 000$. |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 1 Krimmi_Hundrad, Arnaldur_Indridason Lenging_broka, Hallgerdur Dune, Herbert_S_Wilf Lenging_broka |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 3 Undirstodur, Isaac_Aasimov Sjalfstaett_folk, Halldor_Laxness Britt_Marie_heilsar, Fredrik_Backman Eg_velmenni, Isaac_Aasimov Madur_sem_heitir_Ove, Fredrik_Backman Undirstodur Madur_sem_heitir_Ove Inngangur_ad_forritun |
5 2 -1 |
