题目描述

有 $n$ 个由前 $m$ 个大写字母组成的长度为 $l$ 的串 $s_{1\cdots n}$。

初始有一个空串 $T$，每秒会随机在 $T$ 的末尾加入一个大写字母，对于第 $j$ 个大写字母，每秒被加入的概率是 $\frac{p_j}{q_j}$，并且有 $\sum_{i=1}^m \frac{p_i}{q_i}=1$。

问每个串 $s_i$ 先于其它所有串在 $T$ 里出现的概率。

输入格式

第一行三个整数 $n,l,m$。

接下来 $m$ 行，每行两个整数 $p,q$，第 $i$ 行的输入表示随机到第 $i$ 个字母的概率是 $\frac{p}{q}$。

接下来 $n$ 行，每行一个长度为 $l$ 的字符串 $s_i$。

输出格式

包括 $n$ 行，第 $i$ 行一个实数表示串 $s_i$ 先于其它所有串在 $T$ 里出现的概率，四舍五入保留两位小数。

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

数据规模与约定

对于 $100\%$ 的数据，$1\leq n,m,l\leq 10$，$0\leq p\leq q\leq 10$ 且 $\gcd(p,q)=1$。