Один из режимов ввода
SMS-сообщений в мобильный телефон требует нажатия по одному разу кнопок, содержащих
буквы слова, которое надо ввести. Например, чтобы ввести слово PHONE, нужно
нажать один раз кнопку 7 (на ней находится буква P, см. рис.), затем один раз
кнопку 4 (на ней находится буква H), затем два раза кнопку 6 (на ней находятся
буквы O и N), и, наконец, один раз кнопку 3 (на ней находится буква E).
Поскольку одна кнопка мобильного телефона соответствует более чем одной букве,
то и полная последовательность нажатий может соответствовать более чем одному
слову. Вам требуется реализовать часть программного обеспечения мобильного
телефона — по заданной последовательности нажатий клавиш выделить из словаря
телефона слова, которые могли подразумеваться пользователем при нажатии такой
последовательности клавиш.
Раскладка клавиатуры мобильного телефона:
В первой строке входного
файла находится последовательность цифр, соответствующая
последовательности нажатий кнопок (не более 20). Во второй строке содержится
число слов в словаре (не более 10 000). Начиная с третьей строки идёт словарь
по одному слову в строке, в лексикографически возрастающем порядке. Длина
каждого слова не превосходит 20. Слова состоят из заглавных латинских букв.
В выходном файле
должен содержаться набор слов словаря, подходящих под заданную
последовательность нажатий кнопок по одному слову в строке, в лексикографически
возрастающем порядке.
Пример
|
STDIN
|
STDOUT
|
|
74663
3
CELL
MOBILE
PHONE
|
PHONE
|
