P3955 [NOIP 2017 Junior] Librarian

NOIP 2017 Junior T2.

Each book in the library has a book code, which is a positive integer, used for quick lookup. Each reader has a request code, also a positive integer. If a book’s code ends with a reader’s request code, then that book is what the reader needs. Xiao D has just become the librarian. She knows the codes of all books in the library and asks you to write a program to, for each reader, find the book with the smallest code among the books they need. If there is no book they need, please output `-1`.

The first line contains two positive integers $n, q$, separated by a space, representing the number of books in the library and the number of readers, respectively. The next $n$ lines each contain a positive integer, representing the code of a book in the library. The next $q$ lines each contain two positive integers separated by a space. The first integer is the length of the reader’s request code, and the second integer is the reader’s request code.

Output $q$ lines. For the $i$-th line, if there exists a book needed by the $i$-th reader, output the smallest book code among those books; otherwise, output -1.

Constraints and Notes For $20\%$ of the testdata, $1 \le n \le 2$. For another $20\%$ of the testdata, $q = 1$. For another $20\%$ of the testdata, the lengths of all readers’ request codes are $1$. For another $20\%$ of the testdata, all book codes are given in ascending order. For $100\%$ of the testdata, $1 \le n \le 1000, 1 \le q \le 1000$, and all book codes and request codes do not exceed $10^7$. Translated by ChatGPT 5