题目描述

周末同学们非常无聊，有人提议，咱们扔硬币玩吧，谁扔的硬币正面次数多谁胜利。

大家纷纷觉得这个游戏非常符合同学们的特色，但只是扔硬币实在是太单调了。

同学们觉得要加强趣味性，所以要找一个同学扔很多很多次硬币，其他同学记录下正反面情况。

用 $ \texttt{H} $ 表示正面朝上， 用 $ \texttt{T} $ 表示反面朝上，扔很多次硬币后，会得到一个硬币序列。比如 $ \texttt{HTT} $ 表示第一次正面朝上，后两次反面朝上。

但扔到什么时候停止呢？大家提议，选出 $ n $ 个同学， 每个同学猜一个长度为 $ m $ 的序列，当某一个同学猜的序列在硬币序列中出现时，就不再扔硬币了，并且这个同学胜利。为了保证只有一个同学胜利，同学们猜的 $ n $ 个序列两两不同。

很快，$ n $个同学猜好序列，然后进入了紧张而又刺激的扔硬币环节。你想知道，如果硬币正反面朝上的概率相同，每个同学胜利的概率是多少。

输入格式

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

输出格式

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

样例

input

3 3
THT
TTH
HTT

output

0.3333333333
0.2500000000
0.4166666667

数据范围与提示

对于 $ 10\% $ 的数据，$ 1 \leq n, m \leq 3 $；
对于 $ 40\% $ 的数据，$ 1 \leq n, m \leq 18 $；
对于另外 $ 20\%$ 的数据，$ n = 2 $；
对于 $ 100\% $ 的数据，$ 1 \leq n, m \leq 300 $。