{"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\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":"\u003cp\u003eWhile roaming the mystic areas of Stonefalls, in order to drop legendary loot, an adventurer was given a quest as follows. He was given an array $$$A \u003d {a_1,a_2,...,a_N }$$$ of length $$$N$$$, and a number $$$K$$$.\u003c/p\u003e\u003cp\u003eDefine array $$$B$$$ as $$$B(q, A) \u003d $$$ { $$$q-a_1, q-a_2, ..., q-a_N$$$ }. Define function $$$F$$$ as $$$F(B,K)$$$ being sum of products of all $$$K$$$-tuples of elements in array $$$B$$$. For example, if the array $$$B$$$ is $$$[2,3,4,5]$$$, and with $$$K\u003d3$$$, sum of products of all 3-tuples is $$$$$$F(B, 3) \u003d 2*3*4+2*3*5+3*4*5+2*4*5$$$$$$\u003c/p\u003e\u003cp\u003eHe was then given a number Q, number of queries of two types: \u003c/p\u003e\u003cul\u003e \u003cli\u003e Type 1: Given $$$q$$$, $$$i$$$, and $$$d$$$ calculate $$$F(B(q, A), K)$$$ where we make change to initial array as $$$A[i] \u003d d$$$. \u003c/li\u003e\u003cli\u003e Type 2: Given $$$q$$$, $$$L$$$, $$$R$$$, and $$$d$$$ calculate $$$F(B(q, A), K)$$$ where we make change to initial array as $$$A[i] \u003d A[i] + d$$$ for all $$$i$$$ in range $$$[L, R]$$$ inclusive. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eAll changes are temporarily made to initial array, and don\u0027t propagate to following queries. Help the adventurer calculate the answer to a quest, and finally get that loot!\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eIn the first two lines, numbers $$$N$$$ ($$$1 \\leq N \\leq 2*10^4$$$) and $$$K$$$ ($$$1 \\leq K \\leq N$$$), the length of initial array $$$A$$$, and tuple size, followed by $$$a_1,a_2,a_3,…,a_N$$$ ($$$0 \\leq a_i \\leq 10^9$$$) , elements of array $$$A$$$, in the next line. Then follows number $$$Q$$$ ($$$Q \\leq 10$$$), number of queries. In the next $$$Q$$$ lines come queries of the form: \u003c/p\u003e\u003cul\u003e \u003cli\u003e 1 q i d, for type 1, \u003c/li\u003e\u003cli\u003e 2 q L R d, for type 2, \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eas explained above ($$$0 \\leq q, d \\leq 10^9, 1 \\leq i,L,R \\leq N$$$)\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint $$$Q$$$ lines, the answers to queries, modulo $$$998244353$$$.\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\n2\n1 2 3 4 5\n3\n1 6 1 1\n1 6 5 2\n2 6 2 3 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e85\n127\n63\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first query array A \u003d [1, 2, 3, 4, 5], B \u003d [5, 4, 3, 2, 1], sum of products of 2-tuples \u003d 85.\u003c/p\u003e\u003cp\u003eIn second query array A \u003d [1, 2, 3, 4, 2], B \u003d [5, 4, 3, 2, 4], sum of products of 2-tuples \u003d 127\u003c/p\u003e\u003cp\u003eIn third query array A \u003d [1, 3, 4, 4, 5], B \u003d [5, 3, 2, 2, 1], sum of products of 2-tuples \u003d 63\u003c/p\u003e"}}]}