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 <= m <= n <= 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 <= l_i <= r_i <= n$ and $r_i -l_i <= 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 <= w_{i , j} <= 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) union (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 <= b_1, b_2, \\\\cdots, b_m <= 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 | <= 10^(-9)$, where $| x |$ means the absolute value of $x$.
In the sample case, the probability matrix $bold(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
respectively.
## Input
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 <= m <= n <= 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 <= l_i <= r_i <= n$ and $r_i -l_i <= 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 <= w_{i , j} <= 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) union (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 <= b_1, b_2, \\\\cdots, b_m <= n$.We guarantee that the sum of $n$ in all test cases is no larger than $2 times 10^6$.
## Output
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 | <= 10^(-9)$, where $| x |$ means the absolute value of $x$.
[samples]
## Note
In the sample case, the probability matrix $bold(P) = (p_(i comma 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 comma 1) p_(2 comma 2) p_(3 comma 3) = 0. 100000000 times 0. 150000000 times 0. 333333333 = 0. 004999999995000$, $p_(2 comma 1) p_(3 comma 2) p_(4 comma 3) = 0. 600000000 times 0. 333333334 times 0. 450000000 = 0. 090000000180000$, $p_(3 comma 1) p_(4 comma 2) p_(5 comma 3) = 0. 333333333 times 0. 000000000 times 0. 000000001 = 0. 000000000000000$ respectively.
**Definitions**
Let $ N, Q \in \mathbb{Z}^+ $ denote the number of guards and security incidents, respectively.
Let $ G = \{ (x_i, y_i) \mid i \in \{1, \dots, N\} \} \subseteq \mathbb{Z}^2 $ be the set of guard coordinates.
Let $ I = \{ (a_j, b_j) \mid j \in \{1, \dots, Q\} \} \subseteq \mathbb{Z}^2 $ be the set of incident coordinates.
**Constraints**
1. $ 1 \le N, Q \le 3 \cdot 10^5 $
2. $ 0 \le x_i, y_i, a_j, b_j \le 5000 $ for all valid indices.
**Objective**
For each incident $ (a_j, b_j) \in I $, compute:
$$
d_j = \min_{(x_i, y_i) \in G} \left( \max(|a_j - x_i|, |b_j - y_i|) \right)
$$
Output $ d_j $ for each $ j \in \{1, \dots, Q\} $.