Comet OJ

C1155 [JSOI2009]有趣的游戏

内存限制：256 MB 时间限制：1000 ms

题目描述

小阳阳发明了一个有趣的游戏：有 $n$ 个玩家，每一个玩家均有一个长度为 $l$ 的字母序列，任何两个玩家的字母序列不同。共有 $m$ 种不同的字母，所有的字母序列都由这 $m$ 种字母构成，为了方便，我们取大写字母的前 $m$ 个字母。例如 $m=3,l=4,ABAA,CBCA$ 为两个合法的字母序列。现在由小阳阳来操控一台神奇的机器，每个时刻机器会随机产生一个字母，其中第 $i$ 种字母随机出来的概率为 $\frac{p_i}{q_i}(0 \le p_i \le q_i)$，显然 $\sum_{k=1}^m \dfrac{p_i}{q_i}=1$。这样 $T$ 个时刻后机器会产生一个长度为 $T$ 的字母序列。如果某个时刻某个玩家发现自己的字母序列在机器产生的字母序列中出现了，“出现”的定义是玩家的字母序列是机器产生的字母序列中连续的一段，那么我们称这个玩家获胜，游戏结束。现在小阳阳感兴趣的一个问题是，每个玩家分别有多大的概率能获得这场游戏的胜利呢？

输入格式

第一行有三个正整数 $n,l,m$ 表示有 $n$ 个人，每个人的字母序列长度均为 $l$，共有 $m$ 个字母。

接下来 $m$ 行，每行有两个非负整数 $p,q$，表示随机到第 $i$ 个字母的概率为 $p/q,q \le p \le q \le 10$ 且 $(p,q)=1$。数据保证 $m$ 个字母的随机概率之和为 $1$。

接下来 $n$ 行，每行有一个长度为 $l$ 的字母序列，表示第 $i$ 个人的字母序列。数据保证所有的字母一定为大写字母的前 $m$ 个且没有两个字母序列完全相同。

$0 \le p,n,l,m \le 10$

输出

包含 $n$ 行，每行包含一个实数，表示第 $i$ 个人获胜的概率，输出结果四舍五入到两位小数。

样例

样例输入 1

3 2 2
1 2
1 2
AB
BA
AA

样例输出 1

0.25
0.50
0.25

样例输入 2

3 4 2
1 2
1 2
AABA
ABAA
BAAA

样例输出 2

0.31
0.33
0.37

提示