407352: GYM102769 L Lost Temple

Professor Alex is an expert in the study of ancient buildings.

When 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.

Each 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$$$.

Here is an example: $$$n = 4, \{l_i\} = \{4,2,3,3\}, \{r_i\} = \{5,5,6,4\}$$$,

Whenever 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 = 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} = \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:

typedef unsigned long long u64;

u64 xorshift128p(u64 &A, u64 &B) {
	u64 T = A, S = B;
	A = S;
	T ^= T << 23;
	T ^= T >> 17;
	T ^= S ^ (S >> 26);
	B = T;
	return T + S;
}
	
void gen(int n, int L, int X, int Y, u64 A, u64 B, int l[], int r[]) {
	for (int i = 1; i <= n; i ++) {
		l[i] = xorshift128p(A, B) % L + X;
		r[i] = xorshift128p(A, B) % L + Y;
		if (l[i] > r[i]) swap(l[i], r[i]);
	}
}

The first line of the input gives the number of test cases, $$$T\ (1 \le T \le 10^4)$$$. $$$T$$$ test cases follow.

For 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$$$.

The 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$$$.

The last line contains two integers $$$A$$$ and $$$B\ (0 \le A,B < 2^{64})$$$, representing the initial seed.

The sum of $$$n$$$ in all test cases doesn't exceed $$$1.2 \times 10^7$$$.

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$$$.

2
4 6
1 1
43 123
13 10
6 1
4 5

Case #1: 52
Case #2: 798322