Рабочее место участника

Много лет назад было достаточно сложно создавать сообщение SMS на мобильном телефоне. Причина заключалась в том, что у телефона меньше кнопок, чем букв в алфавите. Таким образом, большинство символов приходилось набирать, нажимая одну и ту же кнопку несколько раз. Например, чтобы набрать слово "hello", нужно было дважды нажать кнопку 4, два раза 3, три раза 5, еще три раза 5, и, наконец, три раза 6.

Производителям мобильных телефонов пришлось призадуматься над тем, как упростить процедуру ввода текста в мобильный телефон. И решение было найдено. Оно получило название система ввода текста T9. Цифра "9" в названии означает, что вы можете ввести почти любое слово с помощью девяти кнопок, нажимая только по одной кнопке на каждый символ. Идея заключается в том, что вы просто нажимаете кнопки, соответствующие буквам, а программное обеспечение использует встроенный словарь, чтобы найти "наиболее вероятное" слово, соответствующее последовательности нажатий. Например, для ввода слова "hello" вы просто нажимаете кнопки 4, 3, 5, 5 и 6 по одному разу. Конечно, это могло означать и "gdjjm", но в силу того, что такого английского слова не существует, такой вариант интерпретации ввода может быть безопасно игнорирован. Разумеется, если вы хотите ввести слово, которого нет в словаре (к примеру, имя), то вам придется его набрать повторно, но уже используя обычную систему ввода, вручную (manually).

Точнее, при нажатии очередной кнопки телефон должен показать на экранчике наиболее вероятную последовательность символов, соответствующую текущему вводу. Пусть телефон знает слова "idea" и "hello", причем у "idea" вероятность появления больше. Нажимая кнопки 4, 3, 5, 5 и 6, мы увидим "i", "id", "hel", "hell" и, наконец, "hello".

Напишите реализацию системы ввода T9, которая выдает наиболее вероятную последовательность символов после нажатия каждой кнопки. Вероятность последовательности символов определена как сумма вероятностей всех слов в словаре, начинающихся на эту последовательность. Если несколько последовательностей имеют одинаковую вероятность, то предпочтение нужно отдавать первой в лексикографическом порядке. Пользователь должен иметь возможность ввести начало слова. Например, если в словаре только одно слово "hello", то пользователь, нажав 4 и 3, должен увидеть на экране телефона "he", несмотря на то, что такого слова нет в словаре.

На первой строке ввода идет число `w` – количество слов в словаре `(0\ ≤\ w\ ≤\ 1000)`. Далее идут `w` строк, представляющих словарь. В начале каждой из них записано слово, состоящее только из маленьких букв латинского алфавита. Далее следует пробел и целое число `p\ (1≤p≤100)`, обозначающее вероятность встречи слова. Слова даны в алфавитном порядке. Все слова различны и имеют длину не более 100 символов.

На следующей строчке идет число `m\ (0≤m≤100)`. Последующие `m` строк содержат последовательности цифр 2..9 (нажатия на кнопки телефона), заканчивающиеся 1 (конец слова). На каждой строке цифр не более 110.

Для всех последовательностей нажатий кнопок выведите на каждое нажатие в отдельной строке наиболее вероятную последовательность символов (по алгоритму T9). Если ни одно слово не подходит под последовательность нажатий кнопок, выводите строку "MANUALLY".

После каждого блока, соответствующего последовательности нажатий кнопок, выводите пустую строку.

5
hell 3
hello 4
idea 8
next 8
super 3
2
43556771
431

i
id
hel
hell
hello
MANUALLY
MANUALLY

i
id