{"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\u003e汤姆最近喜欢玩一个视频游戏。这个游戏的规则如下。游戏是在一个$$$x$$$轴上进行的。游戏中总共有$$$n+1$$$根柱子,它们从左到右排成一行。这些柱子从$$$0$$$编号到$$$n$$$编号。编号为$$$i$$$的柱子的坐标是$$$x\u003di$$$。游戏中还有一个范围为$$$[n+1,+\\infty)$$$的无限平台。玩家可以通过跳跃到该范围内的任何位置来取得胜利。\u003c/p\u003e\u003cp\u003e玩家从编号为$$$0$$$的柱子开始,并且只能向右跳跃,即坐标必须增加。他只能跳跃到柱子或平台上,否则他将掉入虚空并且\u003cspan class\u003d\"tex-font-style-bf\"\u003e失败\u003c/span\u003e游戏。此外,他的跳跃能力是有限的,每次跳跃的距离不超过$$$p$$$。\u003c/p\u003e\u003cp\u003e除了编号为$$$0$$$的柱子外,其余每根柱子上都会有一个宝藏箱。编号为$$$i$$$的柱子上的宝藏箱里有$$$a_{i} $$$个金币。然而,还有一些陷阱宝箱($$$a_{i}\u0026lt;0$$$),他会失去$$$|a_{i}|$$$个金币。\u003c/p\u003e\u003cp\u003e这个游戏有$$$n$$$个关卡。汤姆只能在第$$$i$$$关的倍数编号的柱子上跳跃。现在有$$$q$$$个查询,每个查询包含一个数字$$$x$$$,询问汤姆在第$$$x$$$关取得胜利时能获得的最大金币数。可能汤姆在路上打开了太多陷阱宝箱导致金币为负数。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含三个整数$$$n$$$、$$$q$$$和$$$p$$$($$$2\\le p\\le n\\le 10^{6}$$$、$$$1\\le q\\le 10^{6}$$$),表示柱子的数量、查询的数量和最长跳跃距离。\u003c/p\u003e\u003cp\u003e第二行包含$$$n$$$个整数$$$a_1,a_2,\\dots,a_n$$$($$$|a_{i}|\\le 10^{9}$$$),表示编号为$$$i$$$的柱子上的金币数量。\u003c/p\u003e\u003cp\u003e接下来的$$$q$$$行,每行包含一个整数$$$x$$$($$$1\\le x\\le n$$$),表示一个查询,询问他在第$$$x$$$关能获得的最大金币数。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e对于每个查询,在单独的一行中输出一个整数,表示答案。如果无法取得胜利,则输出\u003cspan class\u003d\"tex-font-style-tt\"\u003eNoob\u003c/span\u003e。\u003c/p\u003e"}},{"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\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"}},{"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"}}]}