Auto-Complete

Bessie the cow has a new phone and likes sending text messages, but her hooves are large and the screen is small, so she misspells a lot of words. Farmer John agreed to help by writing an auto-complete app that takes the front part of a word and fills in the rest.

The app reads one dictionary. It holds $W$ words, each made only of the lowercase letters a to z, and the letters of all dictionary words add up to at most 1,000,000.

The app answers $N$ queries ($1 \le N \le 10000$). One query is a partial word together with an integer $K_i$. A partial word is also made only of lowercase letters and its length is between 1 and 1,000, and $K_i$ is a positive integer. For query $i$, the app collects every dictionary word that has the $i$th partial word as a prefix, puts those words in alphabetical order, and takes the $K_i$th of them. Call that word the $K_i$th completion of the $i$th partial word.

The first line contains the integers $W$ and $N$.

Each of the next $W$ lines contains one dictionary word. The word written on the $i$th of these lines is the $i$th word of the dictionary.

Each of the next $N$ lines contains an integer $K_i$ and a partial word, separated by one space.

Print $N$ lines. Line $i$ holds the position in the dictionary, an integer between 1 and $W$, of the $K_i$th completion of the $i$th partial word. If that partial word has fewer than $K_i$ completions, print -1 instead.

If the same word sits in the dictionary more than once, alphabetical order alone does not separate the copies. In that case the copy that comes earlier in the dictionary counts as the earlier completion.

In the first example the completions of a are aa, aaa, aab, ab, abc, ac. The fourth completion is ab, on line 3 of the dictionary. The completions of da are daa, dab, dadba, so the second completion is dab, on line 1 of the dictionary. da has only three completions, so it has no fourth one.