Three Kingdoms Go Tournament

The annual "Nongxin Cup" Three Kingdoms Go Tournament is the highest-level go competition in the world, featuring the three national teams: A, B and C. Each team has n players (in the actual contest n = 5, but n can be small for this problem) labeled A1, A2, …, An; B1, B2, …, Bn; C1, C2, …, Cn. The tournament is played according to the following rules:

1. The first player to appear for each team is fixed as the n-th player, i.e. A_n, B_n and C_n.
2. Each match has a winner and a loser. The loser is eliminated.
3. A team is chosen uniformly at random; that team gets a bye in the first round. The remaining two teams’ n-th players play the first match.
4. The winner of the first match then plays against the n-th player of the team that got a bye in the second match. For example, if C_n beats A_n in the first match then C_n will play against B_n in the second match.
5. From the third match on, the team that did not participate in the previous match chooses one of its remaining (non‐eliminated) players to play against the winner of the previous match.
6. This process continues until one team has lost all of its players.
7. When only two teams remain, after each match the losing team chooses one of its remaining players to face the winner in the next match.
8. The tournament ends when all players from one team are eliminated; the remaining team wins the Nongxin Cup.

Each pair of players from different teams has a known win probability. For any two players Q and R from different teams, the probability that Q defeats R is given as p (and R beats Q with probability 1-p). In particular, the win probabilities between teams are provided as three matrices. For example, the matrix for team A versus team B is an n × n matrix where the element in the i-th row and j-th column represents the probability that A_i beats B_j. (Similarly, the matrix for team A versus team C and the matrix for team B versus team C are given; note that the probability of the reverse outcome is 1 minus the provided value.)

Assume that team A is extremely strong so that teams B and C will make every decision in order to minimize team A's chances of winning, while team A makes every decision to maximize its winning probability. Let E_A denote team A's expected probability to win the tournament under optimal play. In a match between players Q and R where Q wins with probability p, if Q wins the match then the expected probability becomes E₁ and if R wins then it is E₂, so that:

$$E_A = p \times E_1 + (1-p) \times E_2.$$

The game is solved by recursively computing these expectations and taking into account that team A will choose the option that maximizes E_A, while teams B and C choose to minimize E_A. When all players of team B and C are eliminated, the winning probability is 1; if all players of team A are eliminated then it is 0.

Note: For simplicity, in the input test cases for this problem you may assume n = 1. In this situation there is no decision to be made because each team has only one player. The tournament then proceeds as follows:

• If team A gets a bye (with probability 1/3), then teams B and C play. Suppose in the matrix for team B vs team C the probability that B₁ beats C₁ is x. Then the winner plays team A. When A faces B, the probability A₁ wins is given by the (1,1) entry in the A vs B matrix (a), and when A faces C, the winning probability is the (1,1) entry in the A vs C matrix (b). Thus, team A's contribution in this branch is:

$$\frac{1}{3}\Bigl( x \times a + (1-x) \times b \Bigr). $$

• If team B gets the bye (with probability 1/3), then teams A and C play. Only if A wins (with probability b from the A vs C matrix) does A continue to face B (with winning probability a). The contribution here is \( \frac{1}{3}(b \times a) \).
• If team C gets the bye (with probability 1/3), then teams A and B play. If A wins (with probability a from the A vs B matrix) then A faces C (with winning probability b from the A vs C matrix). The contribution in this branch is \( \frac{1}{3}(a \times b) \).

Thus, for n = 1 the expected winning probability for team A is:

$$E_A = \frac{1}{3}\Bigl( x\,a + (1-x)\,b + 2ab \Bigr). $$

Your task is to compute E_A (as a percentage) given the three matrices. In the test cases for this problem, n will be 1.

inputFormat

Input consists of the following:

• First line: an integer n (for the test cases herein, n = 1).
• The next n lines: each line contains n floating‑point numbers representing the A vs B win probabilities. The j-th number in the i-th line is the probability that A_i beats B_j.
• The next n lines: each line contains n floating‑point numbers representing the A vs C win probabilities.
• The next n lines: each line contains n floating‑point numbers representing the B vs C win probabilities. (For B vs C, the j-th number in the i-th line is the probability that B_i beats C_j.)

All probabilities are given as decimals between 0 and 1.

outputFormat

Output a single line containing the expected winning probability for team A (in percentage) under optimal play. The answer should be accurate to at least 8 decimal places.

sample

1
0.7
0.6
0.5

49.66666667

</p>