{"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\u003eProfessor Alex is an expert in the study of ancient buildings.\u003c/p\u003e\u003cp\u003eWhen he was surveying an ancient temple, he found ruins containing several fallen stone pillars. There are $$$n$$$ stone pillars in the ruins, numbered $$$1,2,\\cdots,n$$$. For each $$$i \\in \\{1,2,\\cdots,n-1\\}$$$, the $$$(i+1)^{\\rm th}$$$ stone pillar is next to the $$$i^{\\rm th}$$$ stone pillar from west to east. As time went on, some stone pillars were badly destroyed. \u003c/p\u003e\u003cp\u003eEach stone pillar can be regarded as a series of continuous cubic stones, and we label the cubic stones $$$1,2,3,\\cdots,10^9$$$ from south to north. Every two east-west adjacent cubic stones have the same label. The $$$i^{\\rm th}$$$ stone pillar remains cubic stones $$$l_i,l_i+1,\\cdots,r_i$$$. \u003c/p\u003e\u003cp\u003eHere is an example: $$$n \u003d 4, \\{l_i\\} \u003d \\{4,2,3,3\\}, \\{r_i\\} \u003d \\{5,5,6,4\\}$$$,\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/6cc7b0c8f806899daa079515eee37fda?v\u003d1715965589\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eWhenever a year goes by, the outer cubic stone will be destroyed by acid rain. In the above example, those blue squares will disappear one year later. Alex wants to know when the all of cubic stones of the $$$i^{\\rm th}$$$ stone pillar will disappear for each $$$i \u003d 1,2,\\cdots, n$$$. Assume that the $$$i^{\\rm th}$$$ stone pillar will disappear $$$f_i$$$ years later. You need to output the answer: $$$$$$ \\mathrm{answer} \u003d \\sum_{i\u003d1}^{n} f_i \\cdot 3^{i-1} \\bmod 998244353 $$$$$$ Since the number of stone pillars can be very large, we generate the test data in a special way. We will provide five parameters $$$L,X,Y,A,B$$$, and please refer to the code (written in C++) below:\u003c/p\u003e\u003cpre class\u003d\"lstlisting\"\u003e\u003ccode class\u003d\"prettyprint\"\u003etypedef unsigned long long u64;\n\nu64 xorshift128p(u64 \u0026amp;A, u64 \u0026amp;B) {\n\tu64 T \u003d A, S \u003d B;\n\tA \u003d S;\n\tT ^\u003d T \u0026lt;\u0026lt; 23;\n\tT ^\u003d T \u0026gt;\u0026gt; 17;\n\tT ^\u003d S ^ (S \u0026gt;\u0026gt; 26);\n\tB \u003d T;\n\treturn T + S;\n}\n\t\nvoid gen(int n, int L, int X, int Y, u64 A, u64 B, int l[], int r[]) {\n\tfor (int i \u003d 1; i \u0026lt;\u003d n; i ++) {\n\t\tl[i] \u003d xorshift128p(A, B) % L + X;\n\t\tr[i] \u003d xorshift128p(A, B) % L + Y;\n\t\tif (l[i] \u0026gt; r[i]) swap(l[i], r[i]);\n\t}\n}\n\u003c/code\u003e\u003c/pre\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input gives the number of test cases, $$$T\\ (1 \\le T \\le 10^4)$$$. $$$T$$$ test cases follow.\u003c/p\u003e\u003cp\u003eFor each test case, the first line contains two integers $$$n\\ (1 \\le n \\le 5 \\times 10^6)$$$ and $$$L\\ (1 \\le L \\le 5 \\times 10^8)$$$, where $$$n$$$ is the number of stone pillars and $$$L$$$ is the number of possible value of $$$l_i$$$ and $$$r_i$$$.\u003c/p\u003e\u003cp\u003eThe second line contains two integers $$$X$$$ and $$$Y\\ (1 \\le X,Y \\le 5 \\times 10^8)$$$, where $$$X$$$ is the minimum possible value of $$$l_i$$$ and $$$Y$$$ is the minimum possible value of $$$r_i$$$.\u003c/p\u003e\u003cp\u003eThe last line contains two integers $$$A$$$ and $$$B\\ (0 \\le A,B \u0026lt; 2^{64})$$$, representing the initial seed.\u003c/p\u003e\u003cp\u003eThe sum of $$$n$$$ in all test cases doesn\u0027t exceed $$$1.2 \\times 10^7$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case, output one line containing \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eCase #x: y\u003c/span\u003e\", where $$$\\texttt{x}$$$ is the test case number (starting from $$$1$$$), and $$$\\texttt{y}$$$ is the answer 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\u003e2\n4 6\n1 1\n43 123\n13 10\n6 1\n4 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 52\nCase #2: 798322\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}