Problem Description

Xiao Yangyang invented an interesting game: there are $n$ players, and each player has a letter sequence of length $l$. Any two players' letter sequences are different. There are $m$ different letters in total, and all sequences are made up of these $m$ letters. For convenience, we use the first $m$ uppercase letters.

For example, when $m=3,l=4$, $\texttt{ABAA}$ and $\texttt{CBCA}$ are two valid sequences.

Now Xiao Yangyang controls a magical machine. At each moment, the machine randomly generates one letter, and the probability that the $i$-th letter is generated is $\dfrac{p_i}{q_i}$. Obviously, $\sum \limits_{k=1}^m \dfrac{p_i}{q_i}=1$.

After $T$ moments, the machine will generate a letter sequence of length $T$.

If at some moment a player finds that their letter sequence appears in the sequence generated by the machine, where “appears” means the player's sequence is a continuous substring of the machine's sequence, then we say this player wins and the game ends.

Now Xiao Yangyang is interested in this question: what is the probability that each player wins this game?

Input Format

The first line contains three positive integers $n,l,m$, meaning there are $n$ people, each letter sequence has length $l$, and there are $m$ letters in total.

The next $m$ lines each contain two non-negative integers $p, q$, meaning the probability of randomly getting the $i$-th letter is $\frac{p}{q}$.

The next $n$ lines each contain a letter sequence of length $l$, representing the $i$-th person's letter sequence.

Output Format

Output $n$ lines. Each line contains one real number, representing the probability that the $i$-th person wins. Round the output to two decimal places.

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

Hint

Constraints: $1 \leq n,l,m \leq 10$, $0 \leq p_i \leq q_i \leq 10$ and $\gcd(p,q) = 1$。

Translated by ChatGPT 5