Description

你有一个笨机器人，你打算让它与 $n$ 个机器人玩游戏。

在游戏中有一个 $3 \times 3$ 的矩阵 $A$。我们称矩阵中第 $i$ 行第 $j$ 列的数为 $A_{i,j}$。游戏规则如下：

两个玩家同时从 $[1,3]$ 中各选择一个整数。我们称你的机器人选择的数为 $i$，另一个机器人选择的数为 $j$。 得分为 $A_{i,j}$。 在第 $i$ 局游戏中，你的机器人将与第 $i$ 个机器人进行游戏。第 $i$ 个机器人选择 $1$ 的概率为 $p_{i,1}$，选择 $2$ 的概率为 $p_{i,2}$，选择 $3$ 的概率为 $p_{i,3}$。

你的目标是在每局游戏中使得得分的期望值不为负。但你的机器人非常笨，所以它选择 $1$ 的概率为 $q_1$，选择 $2$ 的概率为 $q_2$，选择 $3$ 的概率为 $q_3$，而你不知道 $q_1,q_2,q_3$ 的值。

我们都知道 $q_1+q_2+q_3=1$。如果 $q_1,q_2,q_3$ 是从所有可能的情况下均匀随机选择的，请计算你达到目标的概率。

Input Format

第一行包含一个整数 $n$（$1 \le n \le 10^4$）。

接下来的 $3$ 行每行包含 $3$ 个整数，这些行中的第 $i$ 行的第 $j$ 个整数为 $A_{i,j}$（$-20 \le A_{i,j} \le 20$）。

接下来的 $n$ 行每行包含 $3$ 个实数，这些行中的第 $i$ 行的第 $j$ 个数为 $p_{i,j}$。保证 $p_{i,1}+p_{i,2}+p_{i,3}=1$ 且 $0 \le p_{i,j}$。

Output Format

输出问题的答案。保证答案永远不会是 $0$。

如果你的答案的绝对误差或相对误差不超过 $10^{-2}$，则认为你的答案是正确的。形式上，设你的答案为 $a$，评测系统的答案为 $b$。当且仅当 $\frac{|a-b|}{\max(1,|b|)} \leq 10^{-2}$ 时，你的答案被接受。

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

0.748252

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

0.111111

Hint

在例子 $1$ 中，例如，$(q_1=1,q_2=0,q_3=0)$ 是可以的。在这种情况下，你的机器人将始终选择 $1$，所以无论机器人 $1$ 选择什么数字，得分总是 $1$，这足以达到你的目标。（由 ChatGPT 4o 翻译）