[SDOI2017]硬币游戏

题目描述

周末同学们非常无聊,有人提议,咱们扔硬币玩吧,谁扔的硬币正面次数多谁胜利。 大家纷纷觉得这个游戏非常符合同学们的特色,但只是扔硬币实在是太单调了。 同学们觉得要加强趣味性,所以要找一个同学扔很多很多次硬币,其他同学记录下正反面情况。 用 $H$ 表示正面朝上,用 $T$ 表示反面朝上,扔很多次硬币后,会得到一个硬币序列。比如 $\text{HTT}$ 表示第一次正面朝上,后两次反面朝上。 但扔到什么时候停止呢?大家提议,选出 $n$ 个同学,每个同学猜一个长度为 $m$ 的序列,当某一个同学猜的序列在硬币序列中出现时,就不再扔硬币了,并且这个同学胜利,为了保证只有一个同学胜利,同学们猜的 $n$ 个序列两两不同。 很快,$n$ 个同学猜好序列,然后进入了紧张而又刺激的扔硬币环节。你想知道,如果硬币正反面朝上的概率相同,每个同学胜利的概率是多少。

输入输出格式

输入格式


第一行两个整数 $n,m$。 接下里 $n$ 行,每行一个长度为 $m$ 的字符串,表示第 $i$ 个同学猜的序列。

输出格式


输出 $n$ 行,第 $i$ 行表示第 $i$ 个同学胜利的概率。选手输出与标准输出的绝对误差不超过 $10^{-6}$ 即视为正确。

输入输出样例

输入样例 #1

3 3
THT
TTH
HTT

输出样例 #1

0.3333333333
0.2500000000
0.4166666667

说明

对于 $10\%$ 的数据,$1\le n,m\le 3$。 对于 $40\%$ 的数据,$1\le n,m\le 18$。 另有 $20\%$ 的数据,$n=2$。 对于 $100\%$ 的数据,$1\le n,m\le 300$。