Description

身后的门被敲响，接过天依包回来的一大盒多肉，放下东西贴贴一会儿之后，她们决定把多肉们在阳台上排成一排。

多肉们的高度不尽相同，天依先将一共 $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.$$

注意：本题输入输出方式具有特殊性。详见「输入格式」与「输出格式」。

Input Format

为节省程序输入耗时，序列 $A$ 将在你的程序内部由 xorShift128Plus 和提供的种子生成。下面给出 C++ 语言下的示例程序：

#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$。请使用其他语言的选手自行查阅相关信息实现生成器。

Output Format

为节省程序输出耗时，你的程序应当输出一行一个整数，表示 $\left(\sum_{i=1}^ni\times A_i'\right)\bmod2^{64}$ 的值。

7 20120712 21702102 4

43

10 114514 19198 10

256

Hint

样例 #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$		$25$
$5$		$\le10^9$		$30$

• 特殊性质：保证程序正确生成的序列 $A$ 中不存在相等元素。

• 注意：本题时限为 $0.5\text s$。

• 热知识：《世末歌者》演唱于夏日，显然不在雨水节气。