Putata 是一个热爱吃面的男孩。现在他正在等待伟大的厨师 Budada 为他烹饪最美味的面条。
Budada 为他烹饪的面条可以描述为一个长度为 $n$ 的数组 $a$，其中 $n$ 是偶数。初始时，位置 $i$ 处的酱汁量为 $a_i$。
在一次操作中，Budada 会执行以下过程：
- Budada 将面条对折，面条长度变为 $\frac{n}{2}$，位置 $i$ 处的酱汁量变为位置 $i$ 和 $n - i + 1$ 处酱汁量之和。形式化地，新面条在位置 $i$ 的酱汁量 $b_i$ 满足 $b_i = a_i + a_{n-i+1}$。
- 然后 Budada 将面条拉伸回原始长度，并将酱汁量平均分配。形式化地，新面条在位置 $i$ 的酱汁量 $a'_i$ 满足 $a'_i = \frac{1}{2} \cdot b_{\lceil \frac{i}{2} \rceil}$。
Putata 在面条上有一个最喜欢的点，即某个特定位置 $x$。现在你需要回答 $q$ 次询问。在第 $i$ 次询问中，你需要输出经过 $k$ 次操作后位置 $x$ 处的酱汁量。对于所有询问，$x$ 是相同的，但 $k$ 对于每次询问是分别给出的。
可以证明答案可以表示为一个既约分数 $\frac{x}{y}$，其中 $x$ 和 $y$ 是整数且 $y \not\equiv 0 \pmod{998\,244\,353}$。输出等于 $x \cdot y^{-1} \pmod{998\,244\,353}$ 的整数。换句话说，输出一个整数 $a$，满足 $0 \le a < 998\,244\,353$ 且 $a \cdot y \equiv x \pmod{998\,244\,353}$。
由于输入量很大，你必须使用生成器来生成询问，并且你只需要输出 $\bigoplus_{i=1}^{q} (ans_i \cdot i)$。请注意，此数字不需要对 $998\,244\,353$ 取模。这里，$\oplus$ 表示按位异或运算。
输入格式
第一行包含三个整数 $test$、$T$ 和 $seed$，它们分别是无关变量、测试用例数量和生成测试数据的种子。请注意，$test$ 不会用于解决问题，你可以直接忽略它。生成器代码在下文给出。
对于每个测试用例，输入包含两行。
第一行包含四个整数 $n$、$q$、$x$ 和 $k_{max}$ ($1 \le n \le 2 \cdot 10^6$, $1 \le q \le 5 \cdot 10^7$, $1 \le x \le n$, $1 \le k_{max} \le 10^{18}$)。
第二行包含 $n$ 个整数，第 $i$ 个整数为 $a_i$ ($0 \le a_i < 998\,244\,353$)。
保证 $n \le 2 \cdot 10^6$，$q \le 5 \cdot 10^7$，且 $n$ 为偶数。
输出格式
输出 $T$ 行。第 $i$ 行必须包含第 $i$ 个测试用例的答案。
样例
输入格式 1
0 2 13 4 2 1 3 1 4 2 3 6 2 3 3 6 2 5 3 1 4
输出格式 1
5 499122191
说明
在第一个测试用例中，初始时 $\{a_i\}$ 为 $\{1, 4, 2, 3\}$。
- 一次操作后，变为 $\{2, 2, 3, 3\}$。
- 两次操作后，变为 $\{\frac{5}{2}, \frac{5}{2}, \frac{5}{2}, \frac{5}{2}\}$。
- 生成的询问为：
- 位置为 $x = 1$；
- 第一次询问：$k = 0, a_x = 1$；
- 第二次询问：$k = 1, a_x = 2$；
- 答案为 $(1 \cdot 1) \oplus (2 \cdot 2) = 5$。
在第二个测试用例中，初始时 $\{a_i\}$ 为 $\{6, 2, 5, 3, 1, 4\}$。
- 一次操作后，变为 $\{5, 5, \frac{3}{2}, \frac{3}{2}, 4, 4\}$。
- 两次操作后，变为 $\{\frac{9}{2}, \frac{9}{2}, \frac{9}{2}, \frac{9}{2}, \frac{3}{2}, \frac{3}{2}\}$。
- 生成的询问为：
- 位置为 $x = 3$；
- 第一次询问：$k = 2, a_x = \frac{9}{2}$，且 $\frac{9}{2} \equiv 499\,122\,181 \pmod{998\,244\,353}$；
- 第二次询问：$k = 0, a_x = 5$。
- 答案为 $(499\,122\,181 \cdot 1) \oplus (5 \cdot 2) = 499\,122\,181 \oplus 10 = 499\,122\,191$。
生成器代码如下：
#include <bits/stdc++.h>
using namespace std;
unsigned long long rd (unsigned long long &x) {
x ^= (x << 13);
x ^= (x >> 7);
x ^= (x << 17);
return x;
}
int main () {
int test, T;
unsigned long long seed;
scanf("%d%d%llu", &test, &T, &seed);
for (int Case = 1; Case <= T; Case ++) {
int n, q, x;
long long k_max;
scanf("%d%d%d%lld", &n, &q, &x, &k_max);
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= q; i ++) {
long long k = rd(seed) % k_max;
/*
Code your solution here.
*/
}
}
}