{"trustable":true,"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\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eIn this problem you will have to deal with a real algorithm that is used in the VK social network.\u003c/span\u003e\u003c/p\u003e\u003cp\u003eAs in any other company that creates high-loaded websites, the VK developers have to deal with request statistics regularly. An important indicator reflecting the load of the site is the mean number of requests for a certain period of time of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e seconds (for example, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e \u003d 60\u0026nbsp;\u003ci\u003eseconds\u003c/i\u003e \u003d 1\u0026nbsp;\u003ci\u003emin\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e \u003d 86400\u0026nbsp;\u003ci\u003eseconds\u003c/i\u003e \u003d 1\u0026nbsp;\u003ci\u003eday\u003c/i\u003e\u003c/span\u003e). For example, if this value drops dramatically, that shows that the site has access problem. If this value grows, that may be a reason to analyze the cause for the growth and add more servers to the website if it is really needed.\u003c/p\u003e\u003cp\u003eHowever, even such a natural problem as counting the mean number of queries for some period of time can be a challenge when you process the amount of data of a huge social network. That\u0027s why the developers have to use original techniques to solve problems approximately, but more effectively at the same time.\u003c/p\u003e\u003cp\u003eLet\u0027s consider the following formal model. We have a service that works for \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e seconds. We know the number of queries to this resource \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e at each moment of time \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003et\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e). Let\u0027s formulate the following algorithm \u003cspan class\u003d\"tex-font-style-it\"\u003eof calculating the mean with exponential decay\u003c/span\u003e. Let \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e be some real number, strictly larger than one.\u003c/p\u003e\u003cpre class\u003d\"verbatim\"\u003e\u003cbr\u003e// setting this constant value correctly can adjust \u003cbr\u003e// the time range for which statistics will be calculated\u003cbr\u003edouble c \u003d \u003cspan class\u003d\"tex-font-style-it\"\u003esome constant value\u003c/span\u003e; \u003cbr\u003e\u003cbr\u003e// as the result of the algorithm\u0027s performance this variable will contain \u003cbr\u003e// the mean number of queries for the last \u003cbr\u003e// T seconds by the current moment of time\u003cbr\u003edouble mean \u003d 0.0; \u003cbr\u003e\u003cbr\u003efor t \u003d 1..n: // at each second, we do the following:\u003cbr\u003e // \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e is the number of queries that came at the last second;\u003cbr\u003e mean \u003d (mean + \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e / T) / c;\u003cbr\u003e\u003c/pre\u003e\u003cp\u003eThus, the mean variable is recalculated each second using the number of queries that came at that second. We can make some mathematical calculations and prove that choosing the value of constant \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e correctly will make the value of \u003cspan class\u003d\"tex-font-style-tt\"\u003emean\u003c/span\u003e not very different from the real mean value \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e at \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e - \u003ci\u003eT\u003c/i\u003e + 1 ≤ \u003ci\u003ex\u003c/i\u003e ≤ \u003ci\u003et\u003c/i\u003e\u003c/span\u003e. \u003c/p\u003e\u003cp\u003eThe advantage of such approach is that it only uses the number of requests at the current moment of time and doesn\u0027t require storing the history of requests for a large time range. Also, it considers the recent values with the weight larger than the weight of the old ones, which helps to react to dramatic change in values quicker.\u003c/p\u003e\u003cp\u003eHowever before using the new theoretical approach in industrial programming, there is an obligatory step to make, that is, to test its credibility practically on given test data sets. Your task is to compare the data obtained as a result of the work of an approximate algorithm to the real data. \u003c/p\u003e\u003cp\u003eYou are given \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e values \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e, integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e and real number \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e. Also, you are given \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e moments \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ej\u003c/i\u003e ≤ \u003ci\u003em\u003c/i\u003e\u003c/span\u003e), where we are interested in the mean value of the number of queries for the last \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e seconds. Implement two algorithms. The first one should calculate the required value by definition, i.e. by the formula \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/51ae4f3dab75c191cae300b3e2f91b7c?v\u003d1715246458\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e. The second algorithm should calculate the mean value as is described above. Print both values and calculate the relative error of the second algorithm by the formula \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/236aba13e8759ea060f927dd0a621119?v\u003d1715246458\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e, where \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eapprox\u003c/i\u003e\u003c/span\u003e is the approximate value, obtained by the second algorithm, and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ereal\u003c/i\u003e\u003c/span\u003e is the exact value obtained by the first algorithm.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e), integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eT\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e) and real number \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 \u0026lt; \u003ci\u003ec\u003c/i\u003e ≤ 100\u003c/span\u003e) — the time range when the resource should work, the length of the time range during which we need the mean number of requests and the coefficient \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e of the work of approximate algorithm. Number \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ec\u003c/i\u003e\u003c/span\u003e is given with exactly six digits after the decimal point.\u003c/p\u003e\u003cp\u003eThe next line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ea\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003et\u003c/i\u003e\u003c/sub\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e\u003c/span\u003e) — the number of queries to the service at each moment of time.\u003c/p\u003e\u003cp\u003eThe next line contains integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003em\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e) — the number of moments of time when we are interested in the mean number of queries for the last \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e seconds.\u003c/p\u003e\u003cp\u003eThe next line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e ≤ \u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e), representing another moment of time for which we need statistics. Moments \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e are strictly increasing.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003em\u003c/i\u003e\u003c/span\u003e lines. The \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/span\u003e-th line must contain three numbers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ereal\u003c/i\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eapprox\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eerror\u003c/i\u003e\u003c/span\u003e, where:\u003c/p\u003e\u003cul\u003e \u003cli\u003e \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/450a0da4fb46944279373ae82e1709de?v\u003d1715246458\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e is the real mean number of queries for the last \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eT\u003c/i\u003e\u003c/span\u003e seconds; \u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eapprox\u003c/i\u003e\u003c/span\u003e is calculated by the given algorithm and equals \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003emean\u003c/i\u003e\u003c/span\u003e at the moment of time \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003et\u003c/i\u003e \u003d \u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (that is, after implementing the \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ej\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e-th iteration of the cycle); \u003c/li\u003e\u003cli\u003e \u003cimg align\u003d\"middle\" class\u003d\"tex-formula\" src\u003d\"CDN_BASE_URL/7b572dc053cbfbbe6fe2105c28363814?v\u003d1715246458\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e is the relative error of the approximate algorithm. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eThe numbers you printed will be compared to the correct numbers with the relative or absolute error \u003cspan class\u003d\"tex-span\"\u003e10\u003csup class\u003d\"upper-index\"\u003e - 4\u003c/sup\u003e\u003c/span\u003e. It is recommended to print the numbers with at least five digits after the decimal point.\u003c/p\u003e"}},{"title":"Examples","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 1 2.000000\n1\n1\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1.000000 0.500000 0.500000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\u003e11 4 1.250000\n9 11 7 5 15 6 6 6 6 6 6\n8\n4 5 6 7 8 9 10 11\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8.000000 4.449600 0.443800\n9.500000 6.559680 0.309507\n8.250000 6.447744 0.218455\n8.000000 6.358195 0.205226\n8.250000 6.286556 0.237993\n6.000000 6.229245 0.038207\n6.000000 6.183396 0.030566\n6.000000 6.146717 0.024453\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","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\u003e13 4 1.250000\n3 3 3 3 3 20 3 3 3 3 3 3 3\n10\n4 5 6 7 8 9 10 11 12 13\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3.000000 1.771200 0.409600\n3.000000 2.016960 0.327680\n7.250000 5.613568 0.225715\n7.250000 5.090854 0.297813\n7.250000 4.672684 0.355492\n7.250000 4.338147 0.401635\n3.000000 4.070517 0.356839\n3.000000 3.856414 0.285471\n3.000000 3.685131 0.228377\n3.000000 3.548105 0.182702\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}