{"trustable":true,"prependHtml":"\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 async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eLevel up is the task of all online games. It\u0027s very boooooooooring. There is only level up in those games, except level up.\u003cbr\u003eIn a online game, there are N heroes numbered id from 1 to N, each begins with level 1 and 0 Experience. They need to kill monsters to get Exp and level up.\u003cbr\u003e\u003ccenter\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/546b9c049e95ae671ccc88dd3e768dec?v\u003d1715357487\"\u003e\u003c/center\u003e\u003cbr\u003eThere are many waves of monsters, each wave, the heroes with id from li to ri will come to kill monsters and those hero with level k will get ei*k Exp. If one hero\u0027s Exp reach Needk then the hero level up to level k immediately.\u003cbr\u003eAfter some waves, I will query the maximum Exp from li to ri.\u003cbr\u003eNow giving the information of each wave and Needk, please tell me the answer of my query.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line is a number T(1\u0026lt;\u003dT\u0026lt;\u003d30), represents the number of case. The next T blocks follow each indicates a case.\u003cbr\u003eThe first line of each case contains three integers N(1\u0026lt;\u003dN\u0026lt;\u003d10000), K(2\u0026lt;\u003dK\u0026lt;\u003d10) and QW(1\u0026lt;\u003dQW\u0026lt;\u003d10000)each represent hero number, the MAX level and querys/waves number.\u003cbr\u003eThen a line with K -1 integers, Need2, Need3...Needk.(1 \u0026lt;\u003d Need2 \u0026lt; Need3 \u0026lt; ... \u0026lt; Needk \u0026lt;\u003d 10000).\u003cbr\u003eThen QW lines follow, each line start with \u0027W\u0027 contains three integers li ri ei (1\u0026lt;\u003dli\u0026lt;\u003dri\u0026lt;\u003dN , 1\u0026lt;\u003dei\u0026lt;\u003d10000); each line start with \u0027Q\u0027 contains two integers li ri (1\u0026lt;\u003dli\u0026lt;\u003dri\u0026lt;\u003dN)."}},{"title":"Output","value":{"format":"HTML","content":"For each case, output the number of case in first line.(as shown in the sample output)\u003cbr\u003eFor each query, output the maximum Exp from li to ri.\u003cbr\u003eOutput a black line after each case."}},{"title":"Sample","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\u003e2\r\n3 3 5\r\n1 2\r\nW 1 1 1\r\nW 1 2 1\r\nQ 1 3\r\nW 1 3 1\r\nQ 1 3\r\n\r\n5 5 8\r\n2 10 15 16 \r\nW 5 5 9\r\nW 3 4 5\r\nW 1 1 2\r\nW 2 3 2\r\nQ 3 5\r\nW 1 3 8\r\nQ 1 2\r\nQ 3 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1:\r\n3\r\n6\r\n\r\nCase 2:\r\n9\r\n18\r\n25\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eCase 1:\u003cbr\u003eAt first ,the information of each hero is 0(1),0(1),0(1) [Exp(level)]\u003cbr\u003eAfter first wave, 1(2),0(1),0(1);\u003cbr\u003eAfter second wave, 3(3),1(2),0(1);\u003cbr\u003eAfter third wave, 6(3),3(3),1(2);\u003cbr\u003eCase 2:\u003cbr\u003eThe information of each hero finally:\u003cbr\u003e18(5) 18(5) 25(5) 5(2) 9(2)\u003cbr\u003e"}}]}