Problem Description

You have a dumb robot, and you are going to let it play games with $n$ robots.

There is a matrix $A$ with three rows and three columns in the game. We call the number at row $i$ and column $j$ of this matrix $A_{i,j}$. The game proceeds as follows:

Two players each choose an integer from $[1,3]$ simultaneously. Let the number your robot chooses be $i$, and the number the other robot chooses be $j$.
The score is determined by $A_{i,j}$.
In game $i$, your robot will play this game with the $i$-th robot. The $i$-th robot has a probability of choosing $1$ as $p_{i,1}$, a probability of choosing $2$ as $p_{i,2}$, and a probability of choosing $3$ as $p_{i,3}$.

Your goal is to ensure that the expected value of the score is non-negative in each game. However, your robot is very dumb, so it will choose $1$ with probability $q_1$, $2$ with probability $q_2$, and $3$ with probability $q_3$, and you do not know the values of $q_1, q_2, q_3$.

It is known that $q_1 + q_2 + q_3 = 1$. If $q_1, q_2, q_3$ are chosen uniformly at random from all possible cases, please calculate the probability that you will achieve your goal.

Input Format

The first line contains one integer $n$ ($1 \le n \le 10^4$).

Each of the next $3$ lines contains $3$ integers, where the $j$-th integer in the $i$-th of these lines is $A_{i,j}$ ($-20 \le A_{i,j} \le 20$).

Each of the next $n$ lines contains $3$ real numbers, where the $j$-th number in the $i$-th of these lines is $p_{i,j}$. It is guaranteed that $p_{i,1} + p_{i,2} + p_{i,3} = 1$ and $0 \le p_{i,j}$.

Output Format

Output the answer to the problem. It is guaranteed that the answer will never be $0$.

Your answer is considered correct if its absolute or relative error does not exceed $10^{-2}$. Formally, let your answer be $a$, and the jury's answer be $b$. Your answer is accepted if and only if $\frac{|a-b|}{\max(1, |b|)} \leq 10^{-2}$.

Sample Input and Output

Sample Input #1

1
1 1 1
-1 2 1
0 -3 2
0.1 0.6 0.3

Sample Output #1

0.748252

Sample Input #2

8
1 3 -2
0 0 2
-2 2 1
0.1 0.3 0.6
0 0 1
0.5 0.2 0.3
0 0 1
1 0 0
0 0 1
0.33 0.33 0.34
0.16 0.16 0.68

Sample Output #2

0.111111

Notes

In example $1$, for instance, $(q_1=1, q_2=0, q_3=0)$ is acceptable. In this case, your robot will always choose $1$, so regardless of what number robot $1$ chooses, the score will always be $1$, which is sufficient to meet your goal.

见题面 Input 部分

见题面 Output 部分