{"problem":{"name":"B. Sequences Generator","description":{"content":"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 int","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":8000,"memory_limit":1048576},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10195B"},"statements":[{"statement_type":"Markdown","content":"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.\n\nNow 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.\n\nThe 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$.\n\nFor 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.\n\nThe 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)$.\n\nThe 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$.\n\nWe guarantee that the sum of $n$ in all test cases is no larger than $2 times 10^6$.\n\nFor each test case, output a line containing \"_Case #x:_\" (without quotes) at first, where _x_ is the test case number starting from $1$.\n\nAfter 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$.\n\n \n\n   \n\nIn the sample case, the probability matrix $bold(P) = (p_{i , j})$ is\n\n$$\\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}$$\n\nand thus the answers in the output are\n\nrespectively.\n\n## Input\n\nThe 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$.\n\n## Output\n\nFor 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$.\n\n[samples]\n\n## Note\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N, Q \\in \\mathbb{Z}^+ $ denote the number of guards and security incidents, respectively.  \nLet $ G = \\{ (x_i, y_i) \\mid i \\in \\{1, \\dots, N\\} \\} \\subseteq \\mathbb{Z}^2 $ be the set of guard coordinates.  \nLet $ I = \\{ (a_j, b_j) \\mid j \\in \\{1, \\dots, Q\\} \\} \\subseteq \\mathbb{Z}^2 $ be the set of incident coordinates.  \n\n**Constraints**  \n1. $ 1 \\le N, Q \\le 3 \\cdot 10^5 $  \n2. $ 0 \\le x_i, y_i, a_j, b_j \\le 5000 $ for all valid indices.  \n\n**Objective**  \nFor each incident $ (a_j, b_j) \\in I $, compute:  \n$$\nd_j = \\min_{(x_i, y_i) \\in G} \\left( \\max(|a_j - x_i|, |b_j - y_i|) \\right)\n$$  \nOutput $ d_j $ for each $ j \\in \\{1, \\dots, Q\\} $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10195B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}