题目描述

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

输入格式

第一行有三个正整数 $n,l,m$ 表示有 $n$ 个人，每个字母的序列长度均为 $l$，共有 $m$ 个字母。
接下来 $m$ 行，每行有两个非负整数 $p, q$，表示随机到第 $i$ 个字母的概率为 $\frac{p}{q}$。
接下来 $n$ 行，每行有一个长度为 $l$ 的字母序列，表示第 $i$ 个人的字母序列。

输出格式

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

3 2 2
1 2
1 2
AB
BA
AA

0.25
0.50
0.25

3 4 2
1 2
1 2
AABA
ABAA
BAAA

0.31
0.33
0.37

提示

$1 \leq n,l,m \leq 10$，$0 \leq p_i \leq q_i \leq 10$ 且 $\gcd(p,q) = 1$。