Description

On the weekend, the students were very bored. Someone suggested: let’s toss coins; whoever gets more heads wins.

Everyone thought this game suited the students’ style, but simply tossing coins was too monotonous.

To make it more interesting, they decided that one student would toss the coin many times, while the others would record the sequence of heads and tails.

Use $\texttt H$ to denote heads and $\texttt T$ to denote tails. After many tosses, we obtain a coin sequence. For example, $\texttt{HTT}$ means heads on the first toss and tails on the next two.

When should we stop tossing? They proposed that $n$ students each guess a sequence of length $m$. When some student’s guessed sequence appears in the coin sequence, they stop tossing and that student wins. To ensure a unique winner, the $n$ sequences are pairwise distinct.

The $n$ students quickly made their guesses, and the exciting coin-tossing began. You want to know, assuming the coin is fair (heads and tails are equally likely), what is the probability that each student wins.

Input Format

The first line contains two integers $n, m$.

The next $n$ lines each contain a string of length $m$, representing the sequence guessed by the $i$-th student.

Output Format

Output $n$ lines. The $i$-th line contains the probability that the $i$-th student wins. Your answer is accepted if the absolute error does not exceed $10^{-6}$.

3 3
THT
TTH
HTT

0.3333333333
0.2500000000
0.4166666667

Hint

For $10\%$ of the testdata, $1 \le n, m \le 3$.

For $40\%$ of the testdata, $1 \le n, m \le 18$.

Additionally, for $20\%$ of the testdata, $n = 2$.

For $100\%$ of the testdata, $1 \le n, m \le 300$.

Translated by ChatGPT 5