{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eThe 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.\u003c/p\u003e\n\u003cp\u003eNow 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\u0027s passcode for all consecutive subsequence of length $$$m$$$ in a sequence generated by RBM2gDCMC.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe 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$$$.\u003c/p\u003e\n\u003cp\u003eFor 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.\u003c/p\u003e\n\u003cp\u003eThe 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}} \u003d 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}$$$.\u003c/p\u003e\n\u003cp\u003eThe next line contains $$$m$$$ integers, denoted by $$$b_1, b_2, \\cdots, b_m$$$, describing the passcode for Gini Romety\u0027s email, where $$$1 \\leq b_1, b_2, \\cdots, b_m \\leq n$$$.\u003c/p\u003e\n\u003cp\u003eWe guarantee that the sum of $$$n$$$ in all test cases is no larger than $$$2 \\times 10^6$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, output a line containing \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eCase #x:\u003c/span\u003e\" (without quotes) at first, where \u003cspan class\u003d\"tex-font-style-tt\"\u003ex\u003c/span\u003e is the test case number starting from $$$1$$$.\u003c/p\u003e\n\u003cp\u003eAfter 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\u0027s 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\u0027s answer is $$$b$$$, your answer will be considered correct if $$$|a - b| \\le 10^{-9}$$$, where $$$|x|$$$ means the absolute value of $$$x$$$.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n5 3\n1 3 100000000 200000000 700000000\n1 3 600000000 150000000 250000000\n1 3 333333333 333333334 333333333\n3 4 450000000 550000000\n1 3 999999998 1 1\n1 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1:\n0.004999999995000\n0.090000000180000\n0.000000000000000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the sample case, the probability matrix $$$\\mathbf{P} \u003d (p_{i, j})$$$ is\u003c/p\u003e\n\u003cp\u003e$$$$$$\\begin{bmatrix} 0.100000000 \u0026amp; 0.200000000 \u0026amp; 0.700000000 \u0026amp; 0.000000000 \u0026amp; 0.000000000 \\\\ 0.600000000 \u0026amp; 0.150000000 \u0026amp; 0.250000000 \u0026amp; 0.000000000 \u0026amp; 0.000000000 \\\\ 0.333333333 \u0026amp; 0.333333334 \u0026amp; 0.333333333 \u0026amp; 0.000000000 \u0026amp; 0.000000000 \\\\ 0.000000000 \u0026amp; 0.000000000 \u0026amp; 0.450000000 \u0026amp; 0.550000000 \u0026amp; 0.000000000 \\\\ 0.999999998 \u0026amp; 0.000000001 \u0026amp; 0.000000001 \u0026amp; 0.000000000 \u0026amp; 0.000000000 \\end{bmatrix}$$$$$$\u003c/p\u003e\n\u003cp\u003eand thus the answers in the output are\u003c/p\u003e\n\u003cul\u003e\n \u003cli\u003e$$$p_{1, 1} p_{2, 2} p_{3, 3} \u003d 0.100000000 \\times 0.150000000 \\times 0.333333333 \u003d 0.004999999995000$$$,\u003c/li\u003e\n \u003cli\u003e$$$p_{2, 1} p_{3, 2} p_{4, 3} \u003d 0.600000000 \\times 0.333333334 \\times 0.450000000 \u003d 0.090000000180000$$$,\u003c/li\u003e\n \u003cli\u003e$$$p_{3, 1} p_{4, 2} p_{5, 3} \u003d 0.333333333 \\times 0.000000000 \\times 0.000000001 \u003d 0.000000000000000$$$\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp\u003erespectively.\u003c/p\u003e"}}]}