{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eTom likes playing a video game recently. The rules of this game are as follows. The game is played on an $$$x$$$-axis. There are a total of $$$n+1$$$ pillars in the game, which are arranged in a row from left to right. The pillars are numbered from $$$0$$$ to $$$n$$$. The coordinate of the pillar numbered $$$i$$$ is $$$x\u003di$$$. There is also an infinite platform in the game in the range of $$$[n+1,+\\infty)$$$. Players can \u003cspan class\u003d\"tex-font-style-bf\"\u003ewin\u003c/span\u003e by jumping to any position within this range. \u003c/p\u003e\u003cp\u003ePlayers start from the pillar numbered $$$0$$$ and can only jump from left to right, i.e. the coordinates must increase. And he can only jump on the pillars or the platform, otherwise, he will fall into the void and \u003cspan class\u003d\"tex-font-style-bf\"\u003efail\u003c/span\u003e the game. In addition, his jumping ability is limited, and the distance of each jump does not exceed $$$p$$$.\u003c/p\u003e\u003cp\u003eExcept for the pillar numbered $$$0$$$, there will be a treasure chest on each remaining pillar. The treasure chest on the pillar numbered $$$i$$$ will have $$$a_{i} $$$ gold coins. However, there are some trap chests ($$$a_{i}\u0026lt;0$$$) where he will lose $$$|a_{i}|$$$ gold coins. \u003c/p\u003e\u003cp\u003eThis game has $$$n$$$ levels. Tom can only jump to the pillars numbered with multiples of $$$i$$$ in the $$$i$$$-th level. Now there are $$$q$$$ queries, each of which contains a number $$$x$$$, asking the maximum number of gold coins Tom can get when he \u003cspan class\u003d\"tex-font-style-bf\"\u003ewins\u003c/span\u003e at level $$$x$$$. It\u0027s possible that Tom opens too many trap chests on the way and gets negative gold coins. \u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains three integers $$$n$$$, $$$q$$$, and $$$p$$$ ($$$2\\le p\\le n\\le 10^{6}$$$, $$$1\\le q\\le 10^{6}$$$), indicating the number of pillars, the number of queries, and the longest jump distance. \u003c/p\u003e\u003cp\u003eThe second line contains $$$n$$$ integers $$$a_1,a_2,\\dots,a_n$$$ ($$$|a_{i}|\\le 10^{9}$$$), indicating the number of gold coins in the treasure chest on the pillar numbered $$$i$$$.\u003c/p\u003e\u003cp\u003eIn the next $$$q$$$ lines, each line contains an integer $$$x$$$ ($$$1\\le x\\le n$$$), indicating a query of the maximum number of gold coins he can obtain in level $$$x$$$. \u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput one integer in a single line for each query, representing the answer. If it is impossible to win, output \u003cspan class\u003d\"tex-font-style-tt\"\u003eNoob\u003c/span\u003e in a single line.\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\u003e5 3 4\n2 5 -6 -4 3\n1\n2\n3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\n5\n-6\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\u003e10 6 8\n5 4 -6 8 -11 5 -6 4 -7 3\n1\n2\n4\n6\n8\n10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e29\n24\n12\n5\n4\nNoob\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}