Some students were bored on the weekend and suggested playing a coin-tossing game, where the person whose coin lands on heads the most times wins. Everyone felt this game was very characteristic of the students, but simply tossing coins was too monotonous.

The students decided to make it more interesting by having one student toss a coin many times while others record the outcomes.

Let $H$ represent heads and $T$ represent tails. After tossing the coin many times, a sequence of outcomes is obtained. For example, $HTT$ means the first toss was heads, and the next two tosses were tails.

But when should the tossing stop? The students suggest that $n$ students each guess a sequence of length $m$. When the sequence guessed by a student appears in the coin-toss sequence, the tossing stops, and that student wins. To ensure only one student wins, the $n$ sequences guessed by the students are all distinct.

Soon, the $n$ students have finished their guesses, and the game enters the intense and exciting coin-tossing phase. You want to know, assuming the probability of heads and tails is the same, what is the probability that each student wins?

Input

The first line contains two integers $n$ and $m$. The next $n$ lines each contain a string of length $m$, representing the sequence guessed by the $i$-th student.

Output

Output $n$ lines, where the $i$-th line represents the probability that the $i$-th student wins. The absolute error between your output and the standard output should not exceed $10^{-6}$.

Constraints

For 10% of the data, $1 \le n, m \le 3$. For 40% of the data, $1 \le n, m \le 18$. For another 20% of the data, $n = 2$. For 100% of the data, $1 \le n, m \le 300$.

Examples

Input 1

3 3
THT
TTH
HTT

Output 1

0.3333333333
0.2500000000
0.4166666667