RBM 第二代双核微处理器芯片，也称为 RBM2gDCMC，可以生成一个长度为 $n$ 的数字序列。在本题中，RBM2gDCMC 生成的序列中的每个数字都被视为 $1$ 到 $n$ 之间的一个整数。
现在我将向你展示 Gini Romety 邮箱的密码，这是一个长度为 $m$ 的序列，其中的整数在 $1$ 到 $n$ 之间。你需要计算 RBM2gDCMC 生成的序列中，所有长度为 $m$ 的连续子序列与 Gini Romety 的密码相吻合的概率。
输入格式
输入包含多个测试用例。第一行包含一个正整数 $T$，表示测试用例的数量，最多为 $5000$。
对于每个测试用例，第一行包含两个整数 $n$ 和 $m$，满足 $1 \le m \le n \le 3 \times 10^5$，含义如上所述。
接下来的 $n$ 行描述了 RBM2gDCMC 生成序列中所有数字的生成逻辑。其中第 $i$ 行包含两个整数 $l_i$ 和 $r_i$，满足 $1 \le l_i \le r_i \le n$ 且 $r_i - l_i \le 9$，以及随后的 $(r_i - l_i + 1)$ 个整数，记为 $w_{i,l_i}, w_{i,l_i+1}, \dots, w_{i,r_i}$，其中 $0 \le w_{i,j} \le 10^9$ 且 $\sum_j w_{i,j} = 10^9$。
这些数据表明，对于第 $i$ 个数字，其值为 $[1, l_i) \cup (r_i, n]$ 范围内的整数的概率为零，而其值为 $[l_i, r_i]$ 范围内的整数 $j$ 的概率为 $\frac{w_{i,j}}{10^9}$。
下一行包含 $m$ 个整数，记为 $b_1, b_2, \dots, b_m$，描述了 Gini Romety 的邮箱密码，其中 $1 \le b_1, b_2, \dots, b_m \le n$。
我们保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^6$。
输出格式
对于每个测试用例，首先输出一行包含 “Case #x:”，其中 $x$ 是从 $1$ 开始的测试用例编号。
之后，输出 $(n - m + 1)$ 行，其中第 $i$ 行包含一个实数，表示 RBM2gDCMC 生成的序列中从第 $i$ 个数字到第 $(i + m - 1)$ 个数字组成的子序列与 Gini Romety 的邮箱密码相吻合的概率。输出的绝对误差应不超过 $10^{-9}$。准确地说，假设你的答案为 $a$，评测系统的答案为 $b$，如果 $|a - b| \le 10^{-9}$，则你的答案将被视为正确，其中 $|x|$ 表示 $x$ 的绝对值。
样例
输入 1
1 5 3 1 3 100000000 200000000 700000000 1 3 600000000 150000000 250000000 1 3 333333333 333333334 333333333 3 4 450000000 550000000 1 3 999999998 1 1 1 2 3
输出 1
Case #1: 0.004999999995000 0.090000000180000 0.000000000000000
说明
在样例中，概率矩阵 $\mathbf{P} = (p_{i,j})$ 为：
$$ \begin{bmatrix} 0.100000000 & 0.200000000 & 0.700000000 & 0.000000000 & 0.000000000 \\ 0.600000000 & 0.150000000 & 0.250000000 & 0.000000000 & 0.000000000 \\ 0.333333333 & 0.333333334 & 0.333333333 & 0.000000000 & 0.000000000 \\ 0.000000000 & 0.000000000 & 0.450000000 & 0.550000000 & 0.000000000 \\ 0.999999998 & 0.000000001 & 0.000000001 & 0.000000000 & 0.000000000 \end{bmatrix} $$
因此输出中的答案分别为：
- $p_{1,1}p_{2,2}p_{3,3} = 0.100000000 \times 0.150000000 \times 0.333333333 = 0.004999999995000$
- $p_{2,1}p_{3,2}p_{4,3} = 0.600000000 \times 0.333333334 \times 0.450000000 = 0.090000000180000$
- $p_{3,1}p_{4,2}p_{5,3} = 0.333333333 \times 0.000000000 \times 0.000000001 = 0.000000000000000$