Description

Xiao Q and Xiao M recently invented a card game called Monkey War.

At the start, Xiao Q and Xiao M each receive some monkey cards. In each round, the two players independently draw one card uniformly at random from their own current cards to fight. The winner takes both cards used in that round. If one player obtains all the monkey cards, that player wins the whole game; otherwise, the game continues.

After several matches, Xiao Q and Xiao M computed a win-rate table that gives, for every pair of monkey cards, the probability that one card beats the other. Since every fight has a decisive outcome and the win rate does not depend on order, for any two cards A and B, the probability that A beats B plus the probability that B beats A is $1$.

Since he keeps losing to Xiao M, Xiao Q starts to doubt whether the cards he gets can ever win overall. He wants the probability that he wins for every initial allocation of monkey cards he might receive.

Because Xiao Q has tens of thousands of sports plans coming up at the CD City Sports Center, this problem is left to you to solve.

Input Format

The first line contains two positive integers $n$ and $m$, the total number of monkey cards and the number of initial allocations to query.

The next $n$ lines each contain $n$ real numbers with two decimal places. Among these $n$ lines, the number in row $i$, column $j$ is $P_{i,j}$, the probability that card $i$ beats card $j$. It is guaranteed that $P_{i,j} + P_{j,i} = 1$. In particular, $P_{i,i} = 0.5$, which has no special meaning.

The last $m$ lines each contain a length-$n$ 01 string with no spaces, representing an initial allocation of cards. If the $i$-th character is '0', then card $i$ initially belongs to Xiao M; otherwise it belongs to Xiao Q.

Output Format

Output $m$ lines. Each line should contain a real number, rounded to 8 decimal places (print exactly 8 digits after the decimal point), representing Xiao Q’s probability of winning under the corresponding initial allocation.

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

Hint

Scoring method:

• If each line of your output differs from the reference answer by at most $2 \times 10^{-6}$, you will receive credit for that test point; otherwise, you will receive no credit.
• The reference answers differ from the true values by at most $10^{-8}$. Therefore, to be correct, your output should differ from the true values by at most $2 \times 10^{-6} \sim 10^{-8}$.

Constraints:

• For each set of testdata, $n$ takes the following values:

• For 100% of the testdata, $1 \le n \le 100$, $1 \le m \le n^2$. $0 \le P_{i,j} \le 1$, $P_{i,j}$ has exactly 2 decimal places, and $P_{i,j} + P_{j,i} = 1$. The 01 strings that represent initial allocations all have length $n$ and contain no other characters.

Translated by ChatGPT 5