测试数据来自 system/1569

描述

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

格式

输入格式

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

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

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

输出格式

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

样例1

样例输入1

3 2 2
1 2
1 2
AB
BA
AA

样例输出1

0.25
0.50
0.25

样例2

样例输入2

3 4 2
1 2
1 2
AABA
ABAA
BAAA

样例输出2

0.31
0.33
0.37

限制

1s~

提示

[样例1解释]
两种字母A和B, 概率均为1/2。

若前两个字母为AB,BA或AA，均有一个人获胜，获胜概率为1/4；若前两个字母为BB, 那么之后随机到BBA,BBBA,BBBBA, …都一定是BA获胜。因此BA的获胜概率为1/4+1/4=1/2。

[样例2解释]
三个人的获胜概率分别为4/13,17/52,19/52,注意输出结果四舍五入到两位小数。

[数据规模]
30%的数据保证n<=2.
50%的数据保证n<=5.
100%的数据保证n,l,m<=10.

来源

09江苏省队差额选拔第三试