描述

背景

不久之前，在手机上为短消息服务（SMS）创建消息相当麻烦。这是因为手机只有九个按键，而字母表中的字母超过九个，因此大多数字符只能通过多次按同一个键来输入。例如，如果你想输入“hello”，你需要按$4$键两次，$3$键两次，$5$键三次，再按$5$键三次，最后按$6$键三次。这个过程非常繁琐，导致许多人放弃使用短消息服务。

这促使手机制造商尝试寻找一种更简便的方法在手机上输入文本。他们开发的解决方案称为$T9$文本输入。名称中的“$9$”表示你可以仅用九个按键且每个字符只需按一次来输入几乎任意单词。解决方案的思路是，你只需开始按键而不重复，软件会使用内置字典查找与输入“最可能”匹配的单词。例如，输入“hello”只需依次按$4$、$3$、$5$、$5$和$6$键各一次。当然，这也可能是输入“gdjjm”的方式，但由于这不是一个合理的英文单词，可以安全地忽略。通过排除所有其他“不太可能”的解决方案，并仅考虑正确的英文单词，这种方法可以显著加快短消息的编写速度。当然，如果单词不在字典中（如名字），则必须再次使用按键重复手动输入。

图8：手机的数字按键。

更准确地说，每输入一个字符，手机将显示迄今为止找到的最可能的字符组合。假设手机知道单词“idea”和“hello”，且“idea”出现频率更高。依次按下$4$、$3$、$5$、$5$和$6$键，手机会依次显示“i”、“id”，然后切换到“hel”、“hell”，最后显示“hello”。

问题

编写一个$T9$文本输入的实现，在每次按键后提供最可能的字符组合。字符组合的概率定义为字典中所有以该组合开头的单词的概率之和。例如，如果字典包含三个单词“hell”、“hello”和“hellfire”，则组合“hell”的概率是这些单词概率的总和。如果某些组合的概率相同，程序应选择字母顺序排在第一的组合。用户还应能够输入单词的开头部分。例如，如果字典中有单词“hello”，用户可以通过按$4$和$3$键输入“he”，即使该单词未在字典中列出。

输入

第一行包含场景的数量。

每个场景以一行开始，其中包含字典中不同单词的数量$w$（$0 \leq w \leq 1000$）。接下来的$w$行按字母升序给出这些单词。每行以一个由小写字母组成的单词开头，不含空格，后跟一个空格和一个整数$p$（$1 \leq p \leq 100$），表示该单词的概率。单词长度不超过$100$个字母。

字典之后是一行包含一个整数$m$。接下来的$m$行，每行包含最多$100$个十进制数字（$2$到$9$），后跟一个$1$表示“下一个单词”。

输出

每个场景的输出以一行“Scenario #$i$:”开始，其中$i$是从$1$开始的场景编号。

对于场景中的每个数字序列$s$，为$s$中存储的每个按键（除了末尾的$1$）打印一行。在该行中，根据字典中的概率和上述$T9$选择规则，打印最可能的单词前缀。如果字典中没有单词与给定的数字序列匹配，则打印“MANUALLY”代替前缀。

每个数字序列的输出以空行结束，每个场景的输出末尾额外添加一个空行。

输入样例 1

2
5
hell 3
hello 4
idea 8
next 8
super 3
2
435561
43321
7
another 5
contest 6
follow 3
give 13
integer 6
new 14
program 4
5
77647261
6391
4681
26684371
77771

输出样例 1

Scenario #1:
i
id
hel
hell
hello

i
id
ide
idea


Scenario #2:
p
pr
pro
prog
progr
progra
program

n
ne
new

g
in
int

c
co
con
cont
anoth
anothe
another

p
pr
MANUALLY
MANUALLY

来源

Northwestern Europe 2001