单点时限: 2.0 sec
内存限制: 256 MB
有一句句子因为粘贴的时候出现了一点问题空格全部丢失了。现在给一本字典，每个词都对应这个词出现的频率（每十亿）。根据这个频率，我们可以根据下面的公式算出这个词带来的收益 $P(word)$：
$$P(word) = \mathrm{len}^2(word) \cdot \ln (\mathrm{frequency}(word))$$
其中 $\mathrm{frequency}$ 就是上面所提到的频率。$\mathrm{len}$ 指的是单词的长度。
特别的，对于字典中没有出现过的词，$P(word) = 0$。
请对句子进行适当的分割，使得分割得到的所有词收益之和最大。同一个词可以重复出现，收益算作多次。
先给出一本词典，词典的第一行是词条数（词条数约为 $40~000$），下面每行分别是单词和对应出现频率，用空格隔开。单词中只会出现英文字母大小写，不会有多余的空格。每个单词只会出现一次。频率是一个正实数。
所有单词长度之和不超过 $3 \cdot 10^5$，最长单词长度不超过 $30$。
接下来一行一个整数 $T$ $(T \leq 10)$，表示有 $T$ 个查询。
下面 $T$ 行，每行一个句子，句子长度不超过 $5~000$。句子中保证只含有英文字母大小写。注意单词匹配时，不区分大小写。
词典数据来源于 Wikipedia Project Gutenberg（可能需要代理），其中 1-10000 词汇。
查询数据来源于 IELTS Test。
对于每组数据，输出两行。
第一行是一个实数，表示最大能达到的收益。输出和答案相差不超过 $10^{-3}$ 即可认为正确。
第二行输出一连串单词，单词和单词之间用空格隔开。满足：
5 ano 10 ther 30 another 10 an 300 other 20 1 another
112.826670 another
5 ano 10.0 ther 30.0 another 10.0 an 300.0 other 2000.0 1 another
212.837691 an other
样例给出的词典与测试数据有所不同。