Coin Toss Pattern Subsequence Game

A group of students are playing an exciting coin toss game with a twist. One student tosses a fair coin (with equal probability for H for heads and T for tails) repeatedly, while n other students each choose a distinct binary sequence of length m (each character is either H or T). The coin is tossed until one of the chosen sequences appears as a contiguous subsequence in the coin toss sequence. The student whose guessed sequence appears first wins the game.

For example, if the coin toss sequence is HTT, it means the first toss was heads and the next two tosses were tails. If one student’s guess is HT and another’s is TT, then the game ends when HT appears starting from the first toss, and the first student wins.

Assuming the coin is fair, you are to determine the probability that each student's chosen sequence is the one that appears first. It is guaranteed that all guessed sequences are distinct and chosen in such a way that no ambiguity arises (i.e. the game will have a unique winner when any guessed sequence appears).

Hint: This problem can be modeled by constructing an Aho–Corasick automaton for the n patterns. The states of the automaton represent the current matching status. Some states are absorbing (when a full pattern is matched) and others are nonabsorbing. For every nonabsorbing state s, the probability vector f(s) = [u₁(s), u₂(s), …, u_n(s)] satisfies

[ f(s) = \frac{1}{2} f(\delta(s, H)) + \frac{1}{2} f(\delta(s, T)) ]

where \(\delta(s, c)\) is the state transition for coin side c. For absorbing states (where a pattern is completed), the corresponding coordinate in the probability vector is 1 and the others are 0. Use a system of linear equations (or the fundamental matrix of the Markov chain) to compute f(0), the probability vector from the start state.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 10), representing the number of students (i.e. guessed patterns) and the length of each guessed pattern respectively. Each of the next n lines contains a string of length m consisting only of the characters H and T, representing a student's guessed pattern.

outputFormat

Output n lines. The i-th line should contain a floating point number representing the winning probability of the i-th guessed sequence. The answers will be accepted if they have an absolute or relative error no more than 1e-6.

sample

1 1
H

1.000000