Probability of Non‐negative Expected Score

You have a dumb robot that plays a game against n other robots. The game uses a 3 \(\times\) 3 matrix \(A\) with entries \(A_{i,j}\) in \(\LaTeX\) format. In each game, you and your opponent simultaneously choose an integer from \(1\) to \(3\). Your robot chooses \(i\) with probability \(q_i\) (where \(q_1+q_2+q_3=1\)), and the opponent (the i-th robot) chooses \(j\) with probability \(p_{i,j}\). The score for the game is \(A_{i,j}\).

In game \(i\) (\(1 \le i \le n\)), the expected score is given by: \[ E_i = \sum_{r=1}^{3}\sum_{c=1}^{3} q_r\,p_{i,c}\,A_{r,c} \ge 0. \]

Your goal is to choose a probability distribution \((q_1,q_2,q_3)\) (which is unknown and is assumed to be uniformly distributed over the probability simplex) such that for every game the expected score is non‐negative. In other words, letting the set of all valid distributions be \[ \Delta = \{(q_1,q_2,q_3): q_i \ge 0, \; q_1+q_2+q_3=1\}, \] find the probability that a uniformly chosen \((q_1,q_2,q_3)\) from \(\Delta\) satisfies \(E_i \ge 0\) for all \(i = 1, 2, \dots, n\).

Note: For each game, define \[ B_{i,r} = \sum_{c=1}^{3} A_{r,c}\,p_{i,c}, \quad \text{for } r=1,2,3. \] Then the condition for game \(i\) becomes: \[ q_1\,(B_{i,1}-B_{i,3}) + q_2\,(B_{i,2}-B_{i,3}) + B_{i,3} \ge 0. \] Express your answer as a floating point number with at least 6 decimal places of precision.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), the number of games (robots).

The next 3 lines each contain 3 space-separated integers, representing the rows of the matrix \(A\). The entries \(A_{i,j}\) can be any integers.

Then \(n\) lines follow. Each of these lines contains 3 space-separated real numbers \(p_{i,1}\), \(p_{i,2}\), \(p_{i,3}\) representing the probability distribution of the opponent in that game. It is guaranteed that \(p_{i,1}+p_{i,2}+p_{i,3}=1\) for each game.

outputFormat

Output a single floating point number: the probability that a randomly chosen distribution \((q_1,q_2,q_3)\) from the simplex will yield a non-negative expected score for every game. The answer is considered correct if it has an absolute or relative error of at most \(10^{-6}\).

sample

1
0 0 0
0 0 0
0 0 0
0.3 0.4 0.3

1.000000