Problem 2: Auto-complete [Traditional]
У Беси есть новый мобильный телефон, и она любит посылать текстовые сообщения, хотя она часто совершает ошибки набора. Фермер Джон написал для неё приложение, которое автоматически дополняет набранную часть слова до полного слова.
Это приложение имеет доступ к словарю из W слов, каждое из которых состоит из маленьких латинских букв a..z. Общее количество букв во всех словах не превышает 1,000,000. На ввод этому приложению подаётся список из N частичных слов (1<=N<=1000), каждое из которых состоит не более чем из 1000 символов - маленьких латинских букв. Для каждого частичного слова I, также задаётся число Ki, которое означает, что приложение должно найти Ki-ое слово в алфавитном порядке, для которого частичное слово I является префиксом. То есть, если упорядочить все корректные дополнения i-го частичного слова, то приложение должно вывести Ki-ое слово в этой последовательности.
PROBLEM NAME: auto
Формат входных данных
* Строка 1: Два целых числа: W и N.
* Строки 2..W+1: Строка i+1: i-ое слово в словаре.
* Строки W+2..W+N+1: Строка W+i+1: Одно целое число Ki за которым через пробел следует i-ое частичное слово.
Формат выходных данных
* Строки 1..N: Строка i должна содержать индекс внутри словаря (целое число в диапазоне от 1 до W) – Ki-ое завершение (в алфавитном порядке) i-го частичного слова или -1, если имеется менее чем Ki завершений.
Примечание
Завершения a есть {aa,aaa,aab,ab,abc,ac}. 4-ое из них ab, которое перечислено под номером 3 в словаре. Завершения da есть {daa,dab,dadba}, 2-ое завершение – dab, перечисленное под номером 1 в словаре. Нет 4-го завершения строки dab.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10 3
dab
ba
ab
daa
aa
aaa
aab
abc
ac
dadba
4 a
2 da
4 da
|
3
1
-1
|