tip:SPJ暂未配置

题目描述

小 Q 和小 M 最近发明了一种卡牌游戏，叫猴子大战。

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

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

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

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

输入格式

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

接下来有 $n$ 行，每行包含 $n$ 个实数，每个实数保留了两位小数。这 $n$ 行中，其中第 $i$ 行第 $j$ 列的数为 $P_{i,j}$ ，表示第 $i$ 张猴子牌战胜第 $j$ 张猴子牌的概率。保证 $P_{i,j} + P_{j,i} = 1$ 。特别地， $P_{i,i} = 0.5$ ，没有特殊意义。

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

输出格式

输出 $m$ 行，每行一个实数，四舍五入保留八位小数（请强制输出八位浮点数），依次表示每个给定的猴子牌组合下小 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

数据规模与约定

对于 $100\%$ 的数据，保证 $1 \le n \le 100,1 \le m \le n^2$ 。$0 ≤ P_{i,j} ≤ 1$ , $P_{i,j}$ 恰好包含 $2$ 位小数，且 $P_{i,j} + P_{j,i} = 1$ 。表示猴子牌组合的 01串 长度均为 $n$ ，且不含其他字符。

评分方式

你的答案的每一行如果与我们给定的参考答案的差别均不超过 $2 \times 10^{-6}$ ，则获得该测试点的得分，否则不得分。

参考答案保证与真实值的差别不超过 $10 ^ {-8}$ ，因此如果你输出的答案保证与真实值差别不超过 $2 \times 10^{-6} \sim 10 ^ {-8}$ ，才能保证正确。

题目来源

vfleaking提供spj