{"raw_statement":[{"iden":"background","content":"  「天将化雨舒清景，萌动生机待绿田」\n\n---\n\n  在天依面前口口声声说着习惯了，才开学没几天，文化课和乐队训练的压力可是又让阿绫头疼呢。\n\n  浓缩为一个晚上的周末。站在阳台上，摸索朦胧于雨声的城市轮廓。雨水之日的雨，对于眼前的高楼大厦——们，恐怕也难有一些别样的意境吧。\n\n  “雨水节令的雨、白露节令的露、霜降节令的霜、小雪节令的雪各十二钱……”\n\n  胡乱想着，阿绫噗嗤一声笑了出来，“但是不管在哪里，雨中的空气，雨后的初阳，总是清新得叫人欢喜。”向着雨幕笑笑，拨弄这手里的旧吉他，不知不觉哼起那首歌来。\n\n---\n\n  **雨水** 「等凉雨　的温度　将不安燥热中和　寻觅着　风的波折」"},{"iden":"statement","content":"\n\n身后的门被敲响，接过天依包回来的一大盒多肉，放下东西贴贴一会儿之后，她们决定把多肉们在阳台上排成一排。\n\n多肉们的高度不尽相同，天依先将一共 $n$ 盆多肉随意排成一排，从左到右第 $i$ 盆的高度为 $a_i$。为了美观，她希望交换某些多肉的位置，使得由高度组成的序列 $A$ 的**字典序**尽可能小，不过，为了照顾多肉们的感受（？）她要求阿绫只能选取 $A$ 的一个**长度为偶数的子序列**（长度可以为 $0$），交换序列里第 $1$ 盆和第 $2$ 盆，第 $3$ 盆和第 $4$ 盆……的位置，然后放回它们原来的位置中。\n\n苦活交给了阿绫，思考的工作自然交给你啦！请告诉阿绫，仅使用**一次**选取子序列的操作，她能够得到的字典序最小的新高度序列 $A'$。\n\n#### 形式化题意\n\n给定一个长为 $n$ 的整数序列 $A$，下标从 $1$ 开始。你可以**任取一个**自然数 $k$ 以及一个序列 $\\lang 1,2,\\dots,n\\rang$ 的，长度为 $2k~(k\\in\\mathbb N)$ 的**子序列** $P$，并对于所有 $i=1,2,\\dots,k$，交换 $A_{P_{2i-1}}$ 与 $A_{P_{2i}}$ 的值。求在所有可能得到的新序列 $A'$ 中，**字典序** 最小的序列。\n\n**字典序**：对于长度为 $n$ 的序列 $A$ 和 $B$，定义 $A$ 的字典序小于 $B$，当且仅当：\n\n$$\n\\exists i\\in[1,n], (\\forall j\\in[1,i), A_j=B_j)\\land A_i // scanf\n\nconst int MAXN = 712; // Set a right value according to your solution.\nint n, a[MAXN + 1];\n\nnamespace Generator {\n\nunsigned long long k1, k2;\nint thres;\n\ninline unsigned long long xorShift128Plus() {\n unsigned long long k3 = k1, k4 = k2;\n k1 = k4, k3 ^= (k3 << 23), k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);\n return k2 + k4;\n}\n\ninline void generate() {\n for (int i = 1; i <= n; ++i) {\n a[i] = xorShift128Plus() % thres;\n }\n}\n\n} // namespace Generator.\n\nint main() {\n scanf(\"%d\", &n);\n scanf(\"%llu %llu %d\", &Generator::k1, &Generator::k2, &Generator::thres);\n Generator::generate();\n // Now array a[1..n] represents the sequence A in the statement.\n return 0;\n}\n```\n\n输入文件仅有一行，包含四个整数 $n,k_1,k_2,\\textit{thres}$。\n\n程序读入序列长度 $n$，种子 $k_1,k_2$ 和序列值上限 $\\textit{thres}$，用 `xorShift128Plus` 连续生成 $n$ 个随机数，将它们对 $\\textit{thres}$ 取模的值依次赋给 $a_1,a_2,\\cdots,a_n$，得到序列 $A$。请使用其他语言的选手自行查阅相关信息实现生成器。\n"},{"iden":"output","content":"为节省程序输出耗时，你的程序应当输出一行一个整数，表示 $\\left(\\sum_{i=1}^ni\\times A_i'\\right)\\bmod2^{64}$ 的值。\n"},{"iden":"note","content":"#### 样例 #1 解释\n\n生成的序列为 $A=\\lang 1,1,3,0,0,1,3\\rang$，选取 $k=1,P=\\lang 1,5\\rang$, 得到答案序列为 $A'=\\lang 0,1,3,0,1,1,3\\rang$，按照要求计算知答案为 $43$。\n\n#### 样例 #2 解释\n\n生成的序列为 $A=\\lang 2,8,0,6,2,2,1,7,8,3\\rang$，选取 $k=3,P=\\lang 1,3,4,7,8,10\\rang$, 得到答案序列为 $A'=\\lang 0,8,2,1,2,2,6,3,8,7\\rang$，按照要求计算知答案为 $256$。\n\n### 数据规模与约定\n\n**本题采用 Subtask 的计分方式。**\n\n对于 $100\\%$ 的测试数据，$1\\le n\\le10^7$，$2\\le \\textit{thres}\\le10^9$，$0\\le k_1,k_2<2^{64}$。\n\n对于不同的子任务，作如下约定：\n\n | 子任务编号 | $n$ | $\\textit{thres}$ | 特殊性质 | 分值 |\n| :--------: | :-------: | :---------: | :------: | :--: |\n| $1$ | $\\le10^5$ | $\\le10^9$ | **有** | $10$ |\n| $2$ | $\\le20$ | $\\le10$ | 无 | $15$ |\n| $3$ | $\\le10^7$ | $=2$ | 无 | $20$ |\n| $4$ | $\\le10^7$ | $\\le10^7$ | 无 | $25$ |\n| $5$ | $\\le10^7$ | $\\le10^9$ | 无 | $30$ |\n\n- **特殊性质**：保证程序正确生成的序列 $A$ 中不存在相等元素。\n\n- **注意**：本题时限为 $0.5\\text s$。\n\n- ~~热知识：《世末歌者》演唱于夏日，显然不在雨水节气。~~\n"}],"translated_statement":null,"sample_group":[["7 20120712 21702102 4","43"],["10 114514 19198 10","256"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}