题目描述

小 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
0.00000000

提示

【评分方法】

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

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

【数据规模及约定】

对于每组数据，$n$ 的取值如下

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