P8332 [ZJOI2022] Noodles

Ren, Alice, Aya, and Yoko finally managed to prepare the first contest paper after many hardships. According to the original plan, Poor (Kanren) would prepare the second paper. “Oh no, Kanren messaged me saying that after landing she was taken into quarantine for 30 days. She has no computer, so she can’t create the problem set,” Aya suddenly received the bad news. “Then what do we do? We have no idea. We can’t just make it up!” Everyone panicked. Looking at the date, there was only one week left before ZJOI. To find out what happens next, please read the next episode.

Kujo Kanren is a girl who likes eating ramen. One day she went to eat ramen, and she found that the ramen chef pulled for her a noodle of length $n$. It is guaranteed that $n$ is even. Initially, the amount of seasoning at position $i$ is $a_i$. The following process is called one “ramen-pulling”: 1. Fold the noodle in half. The noodle’s length becomes $\frac{n}{2}$. The amount of seasoning at position $i$ becomes the sum of the original seasonings at position $i$ and position $n - i + 1$. If the seasoning at position $i$ of the new noodle is $b_i$, then $b_i = a_i + a_{n - i + 1}$. 2. Stretch the noodle back to the original length $n$. Each position becomes two positions, and the seasoning is split equally. If the seasoning at the current position $i$ is $a'_i$, then $a'_i = \frac{1}{2} \times b_{\left\lceil \frac{i}{2} \right\rceil}$. Now for a fixed $x$, you need to answer $q$ queries. For each query, after the noodle undergoes $k$ “ramen-pulling” operations, find the amount of seasoning at position $x$. You only need to output the result modulo $998244353$. Specifically, if the answer in lowest terms is $\frac{a}{b}$, output $a \times b^{-1} \bmod 998244353$.

The first line contains three positive integers $test, T, seed$, representing the test point ID, the number of datasets, and the generation seed. Then follow $T$ datasets, each consisting of two lines. The first line contains four positive integers $n, q, x, k_{\mathrm{max}}$, representing the noodle length in this dataset, the number of queries, the queried position, and the upper bound for generating $k$ in the queries. The second line contains $n$ non-negative integers. The $i$-th integer $a_i$ represents the initial amount of seasoning at position $i$ on the noodle. To avoid large input and output, the $q$ queries are generated by a generator we provide. Specifically, we provide a C++ code template `noodle_template.cpp` for contestants to use (see the appendix). We also give some explanations here: First, we read from the input two $32$-bit integer variables $\mathit{test}, T$, and one unsigned $64$-bit integer variable $\mathit{seed}$. Then we loop $T$ times, representing the $T$ datasets. In each loop, we process one dataset. We first read three $32$-bit integer variables $n, q, x$, and one $64$-bit integer variable $k_{\mathrm{max}}$. Then we read $n$ $32$-bit integer variables into the array $a_1, \ldots, a_n$. Next is the part that generates $q$ queries. Each time we call the function `rd()`, passing $\mathit{seed}$ by reference. We take the returned value (an unsigned $64$-bit integer) modulo $k_{\mathrm{max}}$ as the query parameter $k$. Note that $\mathit{seed}$ will also be modified.

Output $T$ lines, each line containing one integer representing the answer for that dataset. Specifically, suppose the dataset has $q$ queries, and let the answer to the $i$-th query be $\mathrm{Ans}_i$. You need to output $\bigoplus_{i = 1}^q (\mathrm{Ans}_i \cdot i)$. **Note that you do not need to take modulo here.** $\bigoplus$ denotes the bitwise XOR operator.

**[Sample Explanation #1]** In the first dataset, the initial $\{ a_i \}$ is $\{ 1, 4, 2, 3 \}$. After one operation it becomes $\{ 2, 2, 3, 3 \}$. After two operations it becomes $\left\{ \frac{5}{2}, \frac{5}{2}, \frac{5}{2}, \frac{5}{2} \right\}$. The generated queries are: Queried position: $x = 1$; The first query: $k = 0$, $a_x = 1$; The second query: $k = 1$, $a_x = 2$; So the answer is $(1 \times 1) \oplus (2 \times 2) = 4 \oplus 1 = 5$. In the second dataset, the initial $\{ a_i \}$ is $\{ 6, 2, 5, 3, 1, 4 \}$. After one operation it becomes $\left\{ 5, 5, \frac{3}{2}, \frac{3}{2}, 4, 4 \right\}$. After two operations it becomes $\left\{ \frac{9}{2}, \frac{9}{2}, \frac{9}{2}, \frac{9}{2}, \frac{3}{2}, \frac{3}{2} \right\}$. The generated queries are: Queried position: $x = 3$; The first query: $k = 2$, $a_x = \frac{9}{2}$, $\frac{9}{2} \equiv 499122181 \pmod{998244353}$; The second query: $k = 0$, $a_x = 5$; So the answer is $(499122181 \times 1) \oplus (5 \times 2) = 499122181 \oplus 10 = 499122191$. **[Constraints]** For all test points: $T \le 10$, $\sum n \le 2 \times {10}^6$, $\sum q \le 5 \times {10}^7$, $k_{\mathrm{max}} \le {10}^{18}$, $1 \le x \le n$, $0 \le a_i < 998244353$, $0 \le \mathit{seed} \le 2^{60} - 1$, and $n$ is even. Note that for the sample, the test point ID $\mathit{test}$ is $0$. The specific limits for each test point are shown in the table below: | Test Point ID | $\sum n \le$ | $\sum q \le$ | $k_{\mathrm{max}} \le $ | Special Constraint | |:-:|:-:|:-:|:-:|:-:| | $1$ | $500$ | $500$ | $500$ | None | | $2$ | $2 \times {10}^6$ | $2 \times {10}^6$ | $10$ | None | | $3$ | $2 \times {10}^6$ | $2 \times {10}^6$ | ${10}^{18}$ | $n = 2^k$ | | $4$ | $50$ | $50$ | ${10}^{18}$ | None | | $5 \sim 6$ | $150$ | $150$ | ${10}^{18}$ | None | | $7$ | $2 \times {10}^6$ | $2 \times {10}^6$ | ${10}^{18}$ | $n = 98304$ | | $8 \sim 9$ | $500$ | $500$ | ${10}^{18}$ | None | | $10 \sim 11$ | $5 \times {10}^3$ | $2 \times {10}^6$ | ${10}^{18}$ | None | | $12 \sim 13$ | $2 \times {10}^6$ | $50$ | ${10}^{18}$ | None | | $14 \sim 16$ | ${10}^6$ | ${10}^5$ | ${10}^{18}$ | None | | $17 \sim 18$ | $2 \times {10}^6$ | $2 \times {10}^7$ | ${10}^{18}$ | None | | $19 \sim 20$ | $2 \times {10}^6$ | $5 \times {10}^7$ | ${10}^{18}$ | None | **[Appendix]** ```cpp #include using namespace std; unsigned long long rd (unsigned long long &x) { x ^= (x > 7); x ^= (x