You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Each book in the library has a book code, which is a positive integer used for quick book retrieval.
Each reader has a request code, which is also a positive integer. If a book's code ends with the reader's request code, then this book is what the reader needs.
Little D has just become the library administrator. She knows all the book codes in the library. She asks you to write a program that, for each reader, finds the book with the smallest code that matches their request. If no matching book exists, output $-1$.

Input Format

The first line contains two positive integers $n$ and $q$, separated by a space, representing the number of books in the library and the number of readers.
The next $n$ lines each contain a positive integer, representing a book code in the library.
The next $q$ lines each contain two positive integers, separated by a space. The first integer represents the length of the reader's request code, and the second integer represents the reader's request code.
$1 < n < 1000$, $1 < q < 1000$, all book codes and request codes are no more than $10000000$.

Output Format

Output $q$ lines, each containing one integer. If there exists a book matching the $i$-th reader's request, output the smallest book code that matches the request on the $i$-th line. Otherwise, output $-1$.

Sample

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

23
1123
-1
-1
-1