分配有限资源并满足多种约束的预算分配是一个难题。一个预算方案包含 $t$ 个主题；第 $i$ 个主题包含 $n_i$ 个项目。对于每个主题，其最优的相对资金分配是已知的。主题 $i$ 的最优相对分配是一个实数列表 $p_{i,j}$，其中 $\sum_{j=1}^{n_i} p_{i,j} = 1$。

令分配给主题 $i$ 中第 $j$ 个项目的金额为 $c_{i,j}$；该主题的总金额为 $C_i = \sum_{j=1}^{n_i} c_{i,j}$。该主题方案的非最优性定义为 $\sum_{j=1}^{n_i} \left| \frac{c_{i,j}}{C_i} - p_{i,j} \right|$。通俗地说，非最优性是分配给主题中所有项目的实际资金比例与最优比例之间的总差异。整个方案的非最优性是所有 $t$ 个主题的非最优性之和。你的任务是最小化总的方案非最优性。

然而，目前尚不清楚可用的确切金额。主题 $i$ 的第 $j$ 个项目已经分配了 $\hat{c}_{i,j}$ 美元，且这些金额无法收回。此外，还有 $q$ 个可能的额外未分配金额 $x_k$。对于每一个 $x_k$，你需要计算在所有分配这些额外资金的方式中，总非最优性的最小值。你不需要给项目分配整数金额，任何实数都是可能的，但所有额外资金必须在已分配 $\hat{c}_{i,j}$ 的基础上分配给所有项目。形式化地，对于每个额外金额 $x_k$，你需要找到其分配方案 $d_{i,j}$，使得 $d_{i,j} \ge 0$ 且 $\sum_{i=1}^{t} \sum_{j=1}^{n_i} d_{i,j} = x_k$，从而使最终的预算分配 $c_{i,j} = \hat{c}_{i,j} + d_{i,j}$ 最小化总的方案非最优性。

输入格式

第一行包含两个整数 $t$ ($1 \le t \le 5 \cdot 10^4$) 和 $q$ ($1 \le q \le 3 \cdot 10^5$)，分别表示预算中的主题数量和可能的额外金额数量。

接下来的 $t$ 行包含主题的描述。每行以一个整数 $n_i$ ($2 \le n_i \le 5$) 开头，表示第 $i$ 个主题中的项目数量；随后是 $n_i$ 个整数 $\hat{c}_{i,j}$ ($0 \le \hat{c}_{i,j} \le 10^5$；对于任意 $i$，至少有一个 $\hat{c}_{i,j} > 0$)，表示已经分配给第 $i$ 个主题中第 $j$ 个项目的金额；随后是 $n_i$ 个整数 $p'_{i,j}$ ($1 \le p'_{i,j} \le 1000$)，它们决定了 $p_{i,j}$ 的值，即 $p_{i,j} = p'_{i,j} / \sum_{j=1}^{n_i} p'_{i,j}$，且满足 $\sum_{j=1}^{n_i} p_{i,j} = 1$。

最后一行包含 $q$ 个整数 $x_k$ ($0 \le x_k \le 10^{12}$)，表示第 $k$ 个可能的额外金额。

输出格式

输出 $q$ 个实数，表示对应额外金额 $x_k$ 下的最小非最优性。答案的绝对误差或相对误差不得超过 $10^{-6}$。

样例

输入 1

1 5
3 1 7 10 700 400 100
0 2 10 50 102

输出 1

1.0555555555555556
0.8666666666666667
0.5476190476190478
0.12745098039215708
0.0

输入 2

2 5
3 10 70 100 700 400 100
3 10 30 100 700 400 100
2 10 50 70 110

输出 2

2.2967032967032974
2.216776340655188
1.8690167362600323
1.7301587301587305
1.5271317829457367