{"raw_statement":[{"iden":"statement","content":"Professor Alex is an expert in the study of ancient buildings.\n\nWhen 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)^(upright t h)$ stone pillar is next to the $i^(upright t h)$ stone pillar from west to east. As time went on, some stone pillars were badly destroyed. \n\nEach 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^(upright t h)$ stone pillar remains cubic stones $l_i, l_i + 1, \\\\\\\\cdots, r_i$. \n\nHere is an example: $n = 4, {l_i} = {4, 2, 3, 3}, {r_i} = {5, 5, 6, 4}$,\n\nWhenever 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^(upright t h)$ stone pillar will disappear for each $i = 1, 2, \\\\\\\\cdots, n$. Assume that the $i^(upright t h)$ stone pillar will disappear $f_i$ years later. You need to output the answer: $$ \\mathrm{answer} = \\sum_{i=1}^{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:\n\nThe first line of the input gives the number of test cases, $T \" \"(1 <= T <= 10^4)$. $T$ test cases follow.\n\nFor each test case, the first line contains two integers $n \" \"(1 <= n <= 5 times 10^6)$ and $L \" \"(1 <= L <= 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$.\n\nThe second line contains two integers $X$ and $Y \" \"(1 <= X, Y <= 5 times 10^8)$, where $X$ is the minimum possible value of $l_i$ and $Y$ is the minimum possible value of $r_i$.\n\nThe last line contains two integers $A$ and $B \" \"(0 <= A, B < 2^(64))$, representing the initial seed.\n\nThe sum of $n$ in all test cases doesn't exceed $1. 2 times 10^7$.\n\nFor each test case, output one line containing \"_Case #x: y_\", where $texttt(x)$ is the test case number (starting from $1$), and $texttt(y)$ is the answer modulo $998244353$. \n\n"},{"iden":"input","content":"The first line of the input gives the number of test cases, $T \" \"(1 <= T <= 10^4)$. $T$ test cases follow.For each test case, the first line contains two integers $n \" \"(1 <= n <= 5 times 10^6)$ and $L \" \"(1 <= L <= 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$.The second line contains two integers $X$ and $Y \" \"(1 <= X, Y <= 5 times 10^8)$, where $X$ is the minimum possible value of $l_i$ and $Y$ is the minimum possible value of $r_i$.The last line contains two integers $A$ and $B \" \"(0 <= A, B < 2^(64))$, representing the initial seed.The sum of $n$ in all test cases doesn't exceed $1. 2 times 10^7$."},{"iden":"output","content":"For each test case, output one line containing \"_Case #x: y_\", where $texttt(x)$ is the test case number (starting from $1$), and $texttt(y)$ is the answer modulo $998244353$. "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of stone pillars.  \nLet $ l_i, r_i \\in \\mathbb{Z}^+ $ denote the southmost and northmost labels of cubic stones remaining in pillar $ i $, for $ i \\in \\{1, \\dots, n\\} $.  \nThe height of pillar $ i $ is $ h_i = r_i - l_i + 1 $.  \n\nLet $ f_i \\in \\mathbb{Z}^+ $ be the number of years until pillar $ i $ is completely destroyed, defined as:  \n$$\nf_i = \\min(l_i - 1, \\, r_i - l_i + 1, \\, 10^9 - r_i) + 1\n$$  \n*(Each year, the outermost layer of cubic stones is eroded; the pillar vanishes when the last stone is removed.)*\n\nLet $ X, Y, A, B $ be parameters used to generate $ l_i, r_i $ via a pseudo-random sequence:  \n- $ l_1 = X $, $ r_1 = Y $  \n- For $ i \\geq 2 $:  \n  $$\n  l_i = (A \\cdot l_{i-1} + B) \\bmod L + 1, \\quad r_i = (A \\cdot r_{i-1} + B) \\bmod L + 1\n  $$\n\n**Constraints**  \n1. $ 1 \\leq T \\leq 10^4 $  \n2. $ 1 \\leq n \\leq 5 \\times 10^6 $, $ 1 \\leq L \\leq 5 \\times 10^8 $  \n3. $ 1 \\leq X, Y \\leq 5 \\times 10^8 $, $ 0 \\leq A, B < 2^{64} $  \n4. Total $ \\sum n \\leq 1.2 \\times 10^7 $  \n\n**Objective**  \nCompute:  \n$$\n\\text{answer} = \\left( \\sum_{i=1}^{n} f_i \\cdot 3^{i-1} \\right) \\bmod 998244353\n$$","simple_statement":"You are given n stone pillars in a row. Each pillar i has cubic stones from height l_i to r_i (inclusive). Each year, the outermost layer of stones (top and bottom) erodes away. Find how many years f_i until each pillar i is completely gone. Then compute the answer: sum(f_i * 3^(i-1)) mod 998244353.\n\nThe values l_i and r_i are generated using a pseudo-random generator with parameters L, X, Y, A, B — you must use the given code logic to generate them.\n\nInput: T test cases. For each: n, L, X, Y, A, B.\n\nOutput: For each test case, print \"Case #x: y\" where y is the computed answer.","has_page_source":false}