{"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\"\u003eYou have a sequence $A$ of length $n$ and a positive integer $k$. Initially, all elements in $A$ are set to $0$.\u003cbr\u003eNow there are $q$ operations, these operations can be divided into two types.\u003cbr\u003e$1$ $l$ $r$ $x$ $: \\forall i \\in [l,r] A_i \u003d A_i + x$\u003cbr\u003e$2$ $l$ $r$ $:$ Find $\\min\\limits_{i\u003dl}^{r-k+1} ( \\max\\limits_{j\u003di}^{i+k-1} A_j )$ $(r-l+1 \\geq k)$\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer $T (T \\leq 5)$, denoting the number of test cases.\u003cbr\u003eEach test case contains $q + 2$ lines\u003cbr\u003eThe first line contains three integer $n, k(2 \\leq k \\le n \\leq 5 \\times 10^8)$ and $q(1 \\leq q \\leq 10^5)$.\u003cbr\u003eThe next $q$ lines describe operations of two types:\u003cbr\u003e$1$ $l$ $r$ $x$ $: \\forall i \\in [l,r] A_i \u003d A_i + x$ $(|x| \\leq 10^4)$\u003cbr\u003e$2$ $l$ $r$ $:$ Find $\\min\\limits_{i\u003dl}^{r-k+1} ( \\max\\limits_{j\u003di}^{i+k-1} A_j )$ $(r-l+1 \\geq k)$\u003cbr\u003eIt is guaranteed that the sum of $q$ won\u0027t exceed $2 \\times 10^5$.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each operation of type $2$, output the answer in a single line.\u003cbr\u003e"}},{"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\n5 3 3\r\n1 2 5 2\r\n1 3 4 -1\r\n2 1 4\r\n10 4 10\r\n1 1 6 6\r\n1 3 8 -6\r\n2 2 6\r\n1 4 8 -8\r\n1 4 9 4\r\n1 4 5 -7\r\n2 4 8\r\n1 6 7 8\r\n1 1 3 -2\r\n2 3 7\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n0\r\n-4\r\n4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}