6449：Sequences Generator

The RBM Second Generation of Dual Core Microprocessor Chip, also known as RBM2gDCMC, can generate a digital sequence of length $n$.
Each digit in a sequence provided by RBM2gDCMC is regarded as an integer between $1$ and $n$ in this problem.

Now I will show you the passcode for the email belonging to Gini Romety, which is a sequence of length $m$ with integers between $1$ and $n$.
You are asked to calculate the probabilities of the coincidence with Gini Romety's passcode for all consecutive subsequence of length $m$ in a sequence generated by RBM2gDCMC.

The input contains several test cases, and the first line contains a positive integer $T$ indicating the number of test cases which is up to $5000$.

For each test case, the first line contains two integers $n$ and $m$, satisfying $1 \leq m \leq n \leq 3 \times 10^5$, which are described as above.

The following $n$ lines describe the generating logic for all digits in a sequence built by RBM2gDCMC.
The $i$-th line of them contains two integers $l_i$ and $r_i$, satisfying $1 \leq l_i \leq r_i \leq n$ and $r_i - l_i \leq 9$, and $(r_i - l_i + 1)$ following integers, denoted by $w_{i, l_i}, w_{i, l_i + 1}, \cdots, w_{i, r_i}$, where $0 \leq w_{i, j} \leq 10^9$ and $\sum_{j}{w_{i, j}} = 10^9$.
These data indicate that for the $i$-th digit the probability of being an integer $j$ in $[1, l_i) \cup (r_i, n]$ is zero, and the probability of being an integer $j$ in $[l_i, r_i]$ is $\frac{w_{i, j}}{10^9}$.

The next line contains $m$ integers, denoted by $b_1, b_2, \cdots, b_m$, describing the passcode for Gini Romety's email, where $1 \leq b_1, b_2, \cdots, b_m \leq n$.

We guarantee that the sum of $n$ in all test cases is no larger than $2 \times 10^6$.

For each test case, output a line containing "Case #x:" (without quotes) at first, where x is the test case number starting from $1$.

After that, output $(n - m + 1)$ lines such that the $i$-th of them contains a real number indicating the probability of the coincidence for the passcode of Gini Romety's email and the subsequence of a sequence produced by RBM2gDCMC from the $i$-th digit to the $(i + m - 1)$-th one with an absolute error of at most $10^{-9}$.
Precisely speaking, assume that your answer is $a$ and the jury's answer is $b$, your answer will be considered correct if $|a - b| \le 10^{-9}$, where $|x|$ means the absolute value of $x$.