암소 베시는 새로운 폰으로 메시지 보내는 것을 즐긴다. 큰 소굽으로 작은 문자를 보낼려니 애로 사항이 많다. 그래서 자동 완성 기능 앱을 만들어서 베시를 도와 주려고 한다.

이 앱은 W 개의 단어를 가지고 , 각 단어은 소문자 'a'..'z' 으로 구성되어 있다. 각 단어들의 문자수의 합은 1,000,000 개를 넘지 않는다.

이 앱은 입력으로 N(1 <= N <= 1000) 개의 완성되지 않은 단어를 입력으로 받는다. 각 부분단어는 1000 개를 넘지 않는 소문자이다. 그리고 부분단어 i 와 정수 K_i 를 입력으로 받는다. 이 앱은 알파벳 순서로 앞부분이 일치하는 K 번째 단어를 찾아야 한다. 그리고 이 단어가 입력으로 들어온 순서를 출력 해야 한다.

입력의 예에서 a 로 시작하는 단어의 알파벳 순으로 나열하면 {aa,aaa,aab,ab,abc,ac} , 이 중 네 번째 단어는 ab 이고 , 이 단어는 입력의 3 번째 단어여서 3 을 출력해야 한다.

The auto-completion app has access to a dictionary of W words, each consisting of lowercase letters in the range a..z, where the total number of letters among all words is at most 1,000,000.

The app is given as input a list of N partial words (1 <= N <= 1000), each containing at most 1000 lowercase letters.

Along with each partial word i, an integer K_i is also provided, such that the app must find the (K_i)th word in alphabetical order that has partial word i as a prefix. That is, if one ordered all of the valid completions of the ith partial word, the app should output the completion that is (K_i)th in this sequence.

입력

• Line 1: Two integers: W and N.
• Lines 2..W+1: Line i+1: The ith word in the dictionary.
• Lines W+2..W+N+1: Line W+i+1: A single integer K_i followed by a partial word.

출력

입출력 예

입력

10 3
dab
ba
ab
daa
aa
aaa
aab
abc
ac
dadba
4 a
2 da
4 da

출력

3
1
-1

OUTPUT DETAILS:

The completions of a are {aa,aaa,aab,ab,abc,ac}. The 4th is ab, which is listed on line 3 of the dictionary.  
The completions of da are {daa,dab,dadba}.  The 2nd is dab, listed on line 1 of the dictionary.
There is no 4th completion of da.

출처:USACO 2014 February Contest, Bronze,Silver