{"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\"\u003eAs an elegant and accomplished girl, Bella loves watching stars at night (especially the Polaris). There are totally $n$ stars in the sky. We can define $a_i$ as the initial $brightness$ of $i$-th star. \u003cbr\u003e\u003cbr\u003eAt $t$-th second, the $brightness$ of some stars may change due to stars\u0027 activity. To simplify this problem, we can approximately divide activities into two kinds:\u003cbr\u003e\u003cbr\u003e1. $\\forall i \\in [l,r]$ , the $brightness$ of $i$-th star decreases by $a_i \\\u0026amp; (-a_i)$\u003cbr\u003e2. $\\forall i \\in [l,r], a_i \\neq 0$ , the $brightness$ of $i$-th star increases by $2^k$, where $k$ satisfy $2^k\\leq a_i \u0026lt; 2^{k+1}$\u003cbr\u003e\u003cbr\u003eAlso, Bella has some queries. For each query, she wants to know the $sum$ of $brightness$ of stars in the range $[l,r]$, which means $\\sum_{i\u003dl}^r a_i$\u003cbr\u003e\u003cbr\u003eAs we all know, Bella is a big smart. Thus, she could not solve such difficult problem by herself. Please help her solve this problem and answer her queries.\u003cbr\u003e\u003cbr\u003eSince the answer may be too large, please output the answer modulo $998244353$\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\u003e\u003cbr\u003eFor each test case:\u003cbr\u003e\u003cbr\u003eThe first line contains an integers $n(1 \\leq n \\leq 100000)$, denoting the number of stars .\u003cbr\u003e\u003cbr\u003eThe second line contains $n$ integers $a_1,a_2,\\dots,a_n (1 \\leq a_i \\leq 10^9)$, denoting the initial $brightness$ of stars.\u003cbr\u003e\u003cbr\u003eThe third line contains an integer $q(1 \\leq q \\leq 100000)$, denoting the number of operations.\u003cbr\u003e\u003cbr\u003eEach of the next $q$ lines contains three integers $opt_i,l_i,r_i$, denoting the kind of operations and ranges.\u003cbr\u003e\u003cbr\u003e$opt_i\u003d1$ means Bella\u0027s query.\u003cbr\u003e\u003cbr\u003e$opt_i\u003d2$ means the first kind of stars\u0027 activity.\u003cbr\u003e\u003cbr\u003e$opt_i\u003d3$ means the second kind of stars\u0027 activity.\u003cbr\u003e\u003cbr\u003eIt is guaranteed that for all test cases, $\\sum n \\leq 4 \\times 10^5,\\sum q \\leq 4 \\times 10^5$."}},{"title":"Output","value":{"format":"HTML","content":"For each Bella\u0027s query, output the answer modulo $998244353$ in a single line."}},{"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\u003e1\r\n\r\n5\r\n\r\n5 2 2 9 7\r\n\r\n4\r\n\r\n2 1 5\r\n\r\n1 1 1\r\n\r\n3 1 3\r\n\r\n1 2 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n\r\n14\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}