Problem Description

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.

Input Format

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$.

Output Format

For each test case, output a line containing "Case #x:" (without quotes) at first, where $\text{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$.

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

Case #1:
0.004999999995000
0.090000000180000
0.000000000000000

Hint

In the sample case, the probability matrix $\mathbf{P} = (p_{i, j})$ is

$$\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}$$

and thus the answers in the output are

• $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$

respectively.