{"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":"在SC的故乡——Sakura城,计划建造N座高楼。\u003c/p\u003e\n这些高楼准备排成一行,从左至右高度依次为a[1], a[2] ... a[n]。\u003c/p\u003e\n最初每栋楼的高度都是0,DBMN作为施工队的包工头。\u003c/p\u003e\n在每个阶段,DBMN可以选择一个区间[L, R]带上他的民工兄弟,在此工作。\u003c/p\u003e\n也就是说如果选择了h[l] , h[l +1]... h[r]这段区间,所有的h[i](l \u003c\u003d i \u003c\u003d r)都加一\u003c/p\u003e\n当所有的h[i] \u003d a[i](1 \u003c\u003d i \u003c\u003d n)时,项目竣工。\u003c/p\u003e\n问题来了,房地产开发商Jasmine45有钱任性,她要多次修改她的开发计划。\u003c/p\u003e\n只见她淡淡的说出:1 l r k 四个简简单单的数字,DBMN就只能灰溜溜的去将计划书中的所有a[i](l \u003c\u003d i \u003c\u003d r)都加上k(1 \u003c\u003d k \u003c\u003d 1e5)。\u003c/p\u003e\n最厉害的是,Jasmine45想知道,先建好部分的高楼需要DBMN工作几个阶段。\u003c/p\u003e\n当Jasmine45说:2 l r,DBMN需要先把a[1].. a[l - 1], a[r +1] ... a[n]都看做0,然后告诉Jasmine45他工作多久能够竣工! "}},{"title":"Input","value":{"format":"HTML","content":"第一行输入一个T,表示有T组数据(T \u003c\u003d 1000)\u003c/p\u003e\n每组数据输入n和m,表示计划要建造n座楼,Jasmine45要说m句话(1 \u003c\u003d n,m \u003c\u003d 1e5)\u003c/p\u003e\n接下来输入n个数,表示原计划要建造的楼层高度(1 \u003c\u003d a \u003c\u003d 1e5)。\n然后m句话,表示Jasmine45要如何修改计划或者要问DBMN的问题。\u003c/p\u003e\n保证所有的n和m总和小于1e6,毕竟Jasmine45人狠话不多。"}},{"title":"Output","value":{"format":"HTML","content":"对于每次Jasmine45的问话,帮助DBMN回答她,要多久才能竣工。"}},{"title":"Example","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e1\n5 4\n1 3 1 4 5\n2 1 5\n1 3 4 2\n2 2 4\n2 1 5\n\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e7\n6\n6\n\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}}]}