2631: 手机输入法

以前手机发送短信是一件比较麻烦的事情。那是因为手机只有9个按键而字母有26个，因此，大多数字母需要按多次才能输出来。例如你想输出“hello”，你必须按2次4号键，2次2号键，3次5号键，3次5号键，最后再按3次6号键。这个过程让许多使用短消息服务人非常繁琐。
这使得手机厂商试图努力找到一种更简单的手机输入法。最终他们开发出了一种被称为“T9”的文字输入法。该方法是你按下几个号码键，手机使用一个内置字典寻找“最可能的”单词匹配输入。例如,输入“hello”你只需按按键4、3、5、5、6一次。当然,这也可以输入单词“gdjjm”，但因为这是没有意义的英语单词，软件自动把其排除了。通过排除所有其他“不太可能”解决方案，只显示可能的英语单词，这种方法可以大大加快写短消息的速度。当然，如果想输入的词不在字典里(像一个名字)，那么它就必须按原来的方法输入。

更准确的说，当你在按电话号码键时，软件将展示最可能的字符排列组合。让我们假设电话中的输入软件知道单词“hello”和“idea”经常输入的频率，其中“idea”更经常输入。哪当你一个一个按下键4、3、5、5、6时，软件在你按下4时显示“i”、继续按下3时显示“id”， ，继续按下5时将切换显示“hel”，继续按下5时显示“hell” 最后按下6时显示“hello”。
编写一个实现的T9文字输入法，即每次按键后显示最有可能的字符组合。

第一行是一个数字n，表示在内在字典里有n（0 < n <= 1000）个单词的输入频率记录。
接下来n行，每行包括一个单词和这个单词的使用频率p（1 <= p <= 100），它们之间用一个空格隔开。每个单词只有小写字母组成且长度不超过100。
在这n行后，有一行包含一个整数m（1 <= m <= 100）。接下来m行，每行由一个1至9数字组成的序列，表示输入某个单词时按键顺序。数字序列保证不超过100位，且只有最后一位是数字1。

对于每个数字序列，每按一个数字输出字典里最可能单词的前缀，若有多个前缀频率相同输出字典序小的那个。当在字典里没有单词匹配数字序列时，输出“MANUALLY”。每个数字序列匹配完后输出一空行。

7
another 5
contest 6
follow 3
give 13
integer 6
new 14
program 4
5
77647261
6391
4681
26684371
77771

p
pr
pro
prog
progr
progra
program

n
ne
new

g
in
int

c
co
con
cont
anoth
anothe
another

p
pr
MANUALLY
MANUALLY