#103150. [BZOJ 3150] [Ctsc2013]猴子

tip:SPJ暂未配置 小 Q 和小 M 最近发明了一种卡牌游戏，叫猴子大战。

游戏最初小 Q 和小 M 各会取得一部分猴子牌。每局游戏，他们两个需要分别等概率地从自己的猴子牌中抽取一张进行战斗。获胜的一方将获得双方的猴子牌。如果一方获得了所有的猴子牌，则该方获得整场游戏的胜利。否则游戏将一直进行下去。

在进行了若干场比赛以后，小 Q 和小 M 算出了一张胜率表，为每张猴子牌之间进行战斗双方获胜的概率。由于每场战斗一定会决出胜负，而且胜率不受先后顺序的影响，因此对于任意的两张猴子牌 和 ， 战胜 的概率加 战胜 的概率为 。

由于自己老是输给小 M ，小 Q 开始怀疑自己每次拿到的猴子牌是否能获得胜利。他希望求出自己拿到的每种猴子牌组合的获胜的概率。

由于小 Q 接下来还有在 CD 市体育中心数以万计的运动计划，因此这个问题只能交给你来解决了。

输入的第一行包含两个正整数 和 ，表示猴子牌的总张数和需要求的猴子牌组合的个数。

接下来有 行，每行包含 个实数，每个实数保留了两位小数。这 行中，其中第 行第 列的数为 ，表示第 张猴子牌战胜第 张猴子牌的概率。保证 。特别地， ，没有特殊意义。

最后有 行。每行包含一个长度为 的无空格分隔的 01串 ，表示一个猴子牌的组合。其中第 个字符如果为 0 ，表示最初第 张牌在小 M 处，否则表示在小 Q 处。

输出 行，每行一个实数，四舍五入保留八位小数（请强制输出八位浮点数），依次表示每个给定的猴子牌组合下小 Q 获胜的概率。

样例输入

3 4
0.50 0.60 0.40
0.40 0.50 0.70
0.60 0.30 0.50
110
011
111
000

样例输出

0.71304348
0.66086957
1.00000000

对于 的数据，保证 。 , 恰好包含 位小数，且 。表示猴子牌组合的 01串 长度均为 ，且不含其他字符。

评分方式

你的答案的每一行如果与我们给定的参考答案的差别均不超过 ，则获得该测试点的得分，否则不得分。

参考答案保证与真实值的差别不超过 ，因此如果你输出的答案保证与真实值差别不超过 ，才能保证正确。

vfleaking提供spj