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