当前没有测试数据。

5.单词记忆

题目描述

下蛋爷的大脑里面有一个词库，有许许多多的小写英语单词$s_i$构成。对于每个单词，下蛋爷都会记下他以前看到这个单词的次数$c_i$。

当他看到一篇文章的时候，他的特殊记忆方法要求他将整个英语文章过滤空格和标点符号之后并将大写字母转化为小写字母。他在阅读文章的时候会从第一个字开始一直往后面读，当他发现任意一串连续的串是他认识的单词的时候，他就会在他大脑的词库里面给这个单词出现的次数$c_i$加一。

每读完一篇文章之后，下蛋爷会进入思考状态，他会找出他大脑里面出现次数$c_i$最少的那些单词，并以一定的概率$p$决定是否将这些单词忘掉。因为对于出现次数少的串，下蛋爷认为它们是会降低他的记忆效率的。

现在有篇文章给下蛋爷读。为了方便下蛋爷调整他的记忆方法，对于每个下蛋爷大脑内的单词，下蛋爷想知道他在反复朗读这篇文章$k$次后还记得它们的概率是多少。

输入格式

第一行一个整数$n$表示下蛋爷大脑内的单词个数。

接下来$n$行每行一个字符串$s_i$，表示下蛋爷大脑内的单词。

然后一行字符串，表示下蛋爷的文章。

然后一个实数$p$，表示下蛋爷记得这个单词的概率。

然后一个正整数$k$，表示下蛋爷反复朗读该篇文章的次数。

输出格式

共一行，有$n$个实数，表示下蛋爷在反复朗读$k$次该文章后分别记住每一个单词的概率（保留$3$位小数，按照输入顺序输出记住每个单词的概率）。

数据范围与提示

• 对于$10\%$的数据，$1 \leq n \leq 10$；
• 对于$30\%$的数据，$1 \leq n \leq 100$；
• 对于$100\%$的数据，$1 \leq n \leq 200$，每个单词长度不超过$20$，文章长度不超过$10^6$，$0 < p < 1$，$1 \leq k \leq 10^3$。

样例

5
he
she
her
hers
his
hershe
0.30 5

0.163 0.031 0.031 0.031 0.002

说明

单词在文章中出现的次数分别为：2 1 1 1 0

下表为记住每个单词的概率随着阅读轮数的变化情况：