{"raw_statement":[{"iden":"background","content":"忍，爱丽丝，绫和阳子一众千辛万苦地总算出好了第一试，按原先计划，可怜会出第二试。\n\n“不好了，可怜给我发信息说她降落后被拉去隔离 30 天了，没有电脑，出不了题”，绫突然收到了不幸的消息。\n\n“那咋办？没 idea 了，编不出来了啊！” 众人慌作一团。\n\n看了看日期，离 ZJOI 还有一周。\n\n欲知后事如何，请看下回分解。"},{"iden":"statement","content":"九条可怜是一个喜欢吃拉面的女孩子。\n\n有一天她去吃拉面，她发现拉面师傅为她拉的是一个长度为 $n$ 的面条，$n$ 保证是偶数，一开始第 $i$ 个位置调料的数量是 $a_i$。\n\n如下过程称为一次 “拉面”：\n\n1. 将面条对折，面条的长度会变成 $\\frac{n}{2}$，第 $i$ 个位置的调料数量会变为原来第 $i$ 个位置的调料与第 $n - i + 1$ 个位置的调料数量之和，如果新面条第 $i$ 个位置的调料数量为 $b_i$，那么满足 $b_i = a_i + a_{n - i + 1}$。\n2. 将面条拉回原来的长度 $n$，每个位置会变为两个位置，并且调料数量会均分，如果现在的第 $i$ 个位置的调料数量是 $a'_i$，那么 $a'_i = \\frac{1}{2} \\times b_{\\left\\lceil \\frac{i}{2} \\right\\rceil}$。\n\n现在对于一个固定的 $x$，你需要回答 $q$ 个询问，每次面条经过 $k$ 次 “拉面” 后，第 $x$ 个位置的调料数量。你只需要求出答案对 $998244353$ 取模的结果。具体地，即如果答案的最简分数表示为 $\\frac{a}{b}$，输出 $a \\times b^{-1} \\bmod 998244353$。"},{"iden":"input","content":"第一行输入三个正整数 $test, T, seed$，代表测试点编号，数据组数和生成种子。\n\n接下来输入 $T$ 组数据，每组数据包含两行。\n\n第一行输入四个正整数 $n, q, x, k_{\\mathrm{max}}$，代表这组数据中面条的长度，询问的个数，询问的位置和生成询问中 $k$ 的上限。\n\n第二行输入 $n$ 个非负整数，第 $i$ 个整数 $a_i$ 代表初始面条第 $i$ 个位置的调料数量。\n\n为了避免大量的输入与输出，$q$ 个询问由我们提供的一个生成器生成。具体地，我们提供一个由 C++ 书写的代码框架 `noodle_template.cpp` 供选手使用，见附录，同时在这里我们做一定量的说明：\n\n首先我们从数据中依次读入两个 $32$ 位整型变量 $\\mathit{test}, T$，一个无符号 $64$ 位长整型变量 $\\mathit{seed}$。接下来循环 $T$ 次，代表 $T$ 组数据。\n\n在每次循环中，我们对一组数据进行计算。首先依次读入三个 $32$ 位整型变量 $n, q, x$，一个 $64$ 位整型变量 $k_{\\mathrm{max}}$。接下来读入 $n$ 个 $32$ 位整型变量放入数组 $a_1, \\ldots, a_n$ 中。\n\n接下来是生成 $q$ 个询问的部分，每次调用 `rd()` 函数，将 $\\mathit{seed}$ 作为引用参数传入，将返回值（返回值为无符号 $64$ 位长整型）对 $k_{\\mathrm{max}}$ 取模的结果作为该次询问的参数 $k$，注意到 $\\mathit{seed}$ 也会被修改。"},{"iden":"output","content":"输出 $T$ 行，每行一个整数代表该组数据的答案。具体地，假设该组数据有 $q$ 个询问，令第 $i$ 个询问的答案为 $\\mathrm{Ans}_i$，那么需要你输出 $\\bigoplus_{i = 1}^q (\\mathrm{Ans}_i \\cdot i)$，**注意这里不需要取模**。$\\bigoplus$ 指按位异或运算符。"},{"iden":"note","content":"**【样例解释 #1】**\n\n第一组测试数据中，$\\{ a_i \\}$ 初始为 $\\{ 1, 4, 2, 3 \\}$。  \n操作一次后为 $\\{ 2, 2, 3, 3 \\}$。  \n操作两次后为 $\\{ \\frac{5}{2}, \\frac{5}{2}, \\frac{5}{2}, \\frac{5}{2} \\}$。\n\n其中生成询问为：  \n询问位置：$x = 1$；  \n第一个询问：$k = 0$，$a_x = 1$；  \n第二个询问：$k = 1$，$a_x = 2$；  \n答案为 $(1 \\times 1) \\oplus (2 \\times 2) = 4 \\oplus 1 = 5$。\n\n第二组测试数据中，$\\{ a_i \\}$ 初始为 $\\{ 6, 2, 5, 3, 1, 4 \\}$。  \n操作一次后为 $\\{ 5, 5, \\frac{3}{2}, \\frac{3}{2}, 4, 4 \\}$。  \n操作两次后为 $\\{ \\frac{9}{2}, \\frac{9}{2}, \\frac{9}{2}, \\frac{9}{2}, \\frac{3}{2}, \\frac{3}{2} \\}$。\n\n其中生成询问为：  \n询问位置：$x = 3$；  \n第一个询问 $k = 2$，$a_x = \\frac{9}{2}$，$\\frac{9}{2} \\equiv 499122181 \\pmod{998244353}$；  \n第二个询问 $k = 0$，$a_x = 5$；  \n答案为 $(499122181 \\times 1) \\oplus (5 \\times 2) = 499122181 \\oplus 10 = 499122191$。\n\n**【数据范围】**\n\n对于所有测试点：保证 $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$，保证 $n$ 是偶数。\n\n注意，对于样例，测试点编号 $\\mathit{test}$ 为 $0$。\n\n每个测试点的具体限制见下表：\n\n| 测试点编号 | $\\sum n \\le$ | $\\sum q \\le$ | $k_{\\mathrm{max}} \\le $ | 特殊限制 |\n|:-:|:-:|:-:|:-:|:-:|\n| $1$ | $500$ | $500$ | $500$ | 无 |\n| $2$ | $2 \\times {10}^6$ | $2 \\times {10}^6$ | $10$ | 无 |\n| $3$ | $2 \\times {10}^6$ | $2 \\times {10}^6$ | ${10}^{18}$ | $n = 2^k$ |\n| $4$ | $50$ | $50$ | ${10}^{18}$ | 无 |\n| $5 \\sim 6$ | $150$ | $150$ | ${10}^{18}$ | 无 |\n| $7$ | $2 \\times {10}^6$ | $2 \\times {10}^6$ | ${10}^{18}$ | $n = 98304$ |\n| $8 \\sim 9$ | $500$ | $500$ | ${10}^{18}$ | 无 |\n| $10 \\sim 11$ | $5 \\times {10}^3$ | $2 \\times {10}^6$ | ${10}^{18}$ | 无 |\n| $12 \\sim 13$ | $2 \\times {10}^6$ | $50$ | ${10}^{18}$ | 无 |\n| $14 \\sim 16$ | ${10}^6$ | ${10}^5$ | ${10}^{18}$ | 无 |\n| $17 \\sim 18$ | $2 \\times {10}^6$ | $2 \\times {10}^7$ | ${10}^{18}$ | 无 |\n| $19 \\sim 20$ | $2 \\times {10}^6$ | $5 \\times {10}^7$ | ${10}^{18}$ | 无 |\n\n**【附录】**\n\n```cpp\n#include <bits/stdc++.h>\nusing namespace std;\n\nunsigned long long rd (unsigned long long &x) {\n\tx ^= (x << 13);\n\tx ^= (x >> 7);\n\tx ^= (x << 17);\n\treturn x;\n}\n\nint main () {\n\tint test, T;\n\tunsigned long long seed;\n\tscanf(\"%d%d%llu\", &test, &T, &seed);\n\tfor (int Case = 1; Case <= T; Case ++) {\n\t\tint n, q, x;\n\t\tlong long k_max;\n\t\tscanf(\"%d%d%d%lld\", &n, &q, &x, &k_max);\n\t\tvector<int> a(n + 1);\n\t\tfor (int i = 1; i <= n; i ++) {\n\t\t\tscanf(\"%d\", &a[i]);\n\t\t}\n\t\tfor (int i = 1; i <= q; i ++) {\n\t\t\tlong long k = rd(seed) % k_max;\n\t\t\t/∗\n\t\t\tCode your solution here.\n\t\t\t∗/\n\t\t}\n\t}\n}\n```"}],"translated_statement":null,"sample_group":[["0 2 13\n4 2 1 3\n1 4 2 3\n6 2 3 3\n6 2 5 3 1 4\n","5\n499122191\n"],["见附件中的 noodle/noodle_ex2.in","见附件中的 noodle/noodle_ex2.ans"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}