Xiao Q and Xiao M recently invented a card game called Monkey War.
At the beginning of the game, Xiao Q and Xiao M each receive a portion of monkey cards. In each round, they each draw one card from their own set of monkey cards with equal probability to battle. The winner of the round takes both cards. If one player obtains all the monkey cards, that player wins the entire game. Otherwise, the game continues.
After playing several matches, Xiao Q and Xiao M calculated a win-rate table, which shows the probability of one monkey card defeating another. Since every battle must result in a winner and the win rate is independent of the order of play, for any two monkey cards A and B, the probability that A defeats B plus the probability that B defeats A equals $1$.
Because he keeps losing to Xiao M, Xiao Q has started to doubt whether the monkey cards he receives each time can lead to a victory. He wants to calculate the probability of winning for each combination of monkey cards he receives.
Since Xiao Q has thousands of sports plans at the CD City Sports Center, he has left this problem for you to solve.
Input
The first line of the input contains two positive integers $n$ and $m$, representing the total number of monkey cards and the number of monkey card combinations to evaluate.
The next $n$ lines each contain $n$ real numbers, with each number given to two decimal places. The number in the $i$-th row and $j$-th column is $P_{i,j}$, representing the probability that the $i$-th monkey card defeats the $j$-th monkey card. It is guaranteed that $P_{i,j} + P_{j,i} = 1$. Specifically, $P_{i,i} = 0.5$, which has no special significance.
Finally, there are $m$ lines. Each line contains a $01$ string of length $n$ without spaces, representing a combination of monkey cards. If the $i$-th character is $0$, it means the $i$-th card is initially with Xiao M; otherwise, it is with Xiao Q.
Output
Output $m$ lines, each containing a real number rounded to eight decimal places, representing the probability that Xiao Q wins for each given combination of monkey cards.
Examples
Input 1
3 4 0.50 0.60 0.40 0.40 0.50 0.70 0.60 0.30 0.50 110 011 111 000
Output 1
0.71304348 0.66086957 1.00000000 0.00000000
Subtasks
If the difference between each line of your answer and the provided reference answer does not exceed $2 \times 10^{-6}$, you will receive points for that test case; otherwise, you will receive no points.
The reference answer is guaranteed to be within $10^{-8}$ of the true value. Therefore, you must ensure your output is within $2 \times 10^{-6} \sim 10^{-8}$ of the true value to guarantee correctness.
Constraints
For each test case, the values of $n$ are as follows:
| Test Case ID | $n$ | Test Case ID | $n$ |
|---|---|---|---|
| 1 | $n = 2$ | 6 | $n = 20$ |
| 2 | $n = 5$ | 7 | $n = 40$ |
| 3 | $n = 7$ | 8 | $n = 60$ |
| 4 | $n = 8$ | 9 | $n = 80$ |
| 5 | $n = 10$ | 10 | $n = 100$ |
For 100% of the data, it is guaranteed that $1 \le n \le 100$ and $1 \le m \le n^2$. $0 \le P_{i,j} \le 1$, $P_{i,j}$ contains exactly $2$ decimal places, and $P_{i,j} + P_{j,i} = 1$. The $01$ strings representing the monkey card combinations are all of length $n$ and contain no other characters.
The generation method for $P_{i,j}$ is as follows: in a certain environment, using a specific random seed, a pseudo-random integer generator is called continuously until the clock function reaches 1 second. Then, a sequence of random values is taken, modulo $101$, and divided by $100$ to serve as the input data for $P_{i,j}$ where $i < j$.
This generation process is only started once, meaning the data is not regenerated after being viewed. The purpose of this operation is to ensure that each value of $P_{i,j}$ is nearly equiprobable and not subject to human control; you may ignore this paragraph.