Description

周末同学们非常无聊，有人提议，咱们扔硬币玩吧，谁扔的硬币正面次数多谁胜利。大家纷纷觉得这个游戏非常符

合同学们的特色，但只是扔硬币实在是太单调了。同学们觉得要加强趣味性，所以要找一个同学扔很多很多次硬币

，其他同学记录下正反面情况。用H表示正面朝上，用T表示反面朝上，扔很多次硬币后，会得到一个硬币序列。比

如HTT表示第一次正面朝上，后两次反面朝上。但扔到什么时候停止呢？大家提议，选出n个同学，每个同学猜一个

长度为m的序列，当某一个同学猜的序列在硬币序列中出现时，就不再扔硬币了，并且这个同学胜利，为了保证只

有一个同学胜利，同学们猜的n个序列两两不同。很快，n个同学猜好序列，然后进入了紧张而又刺激的扔硬币环节

。你想知道，如果硬币正反面朝上的概率相同，每个同学胜利的概率是多少。

Format

Input

第一行两个整数n,m。

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

1<=n,m<=300

Output

输出n行，第i行表示第i个同学胜利的概率。

输出与标准输出的绝对误差不超过10^-6即视为正确。

Samples

3 3
THT
TTH
HTT

0.3333333333
0.2500000000
0.4166666667