Description

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.

Input Format

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 Format

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.

5 5 
2123 
1123 
23 
24 
24 
2 23 
3 123 
3 124 
2 12 
2 12

23 
1123 
-1 
-1 
-1 

Hint

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