Background

  "The sky will turn to rain to soothe the clear scenery, and budding life waits for green fields."

---

  Even though she kept saying in front of Tianyi that she was used to it, it had only been a few days since school started, and the pressure of cultural classes and band training still gave Ayling a headache.

  All compressed into a weekend night. Standing on the balcony, she groped for the city’s outline blurred within the sound of rain. The rain on a Rainwater day, for the high-rise buildings in front of her—probably could hardly bring out any special mood.

  "The rain of the Rainwater solar term, the dew of the White Dew solar term, the frost of the Frost’s Descent solar term, the snow of the Light Snow solar term, each twelve qian..."

  Thinking messily, Ayling let out a snort of laughter. "But no matter where it is, the air in the rain, the first sunlight after the rain, is always so fresh that it makes people happy." Smiling at the curtain of rain, she fiddled with the old guitar in her hands, and without noticing, she began humming that song.

---

  Rainwater "Waiting for the temperature of cool rain, to balance out the restless heat, searching for the twists of the wind."

Problem Description

The door behind them was knocked. After taking a big box of succulents that Tianyi brought back, and after setting things down and cuddling for a while, they decided to line up the succulents in a row on the balcony.

The succulents have different heights. Tianyi first arranged a total of $n$ pots of succulents in a row at random, where the height of the $i$-th pot from left to right is $a_i$. For aesthetics, she hopes to swap the positions of some succulents so that the sequence $A$ formed by the heights has the smallest possible lexicographical order. However, to take care of the succulents’ feelings (?) she requires that Ayling may only choose an even-length subsequence of $A$ (the length may be $0$), swap the $1$st and $2$nd pots in the subsequence, the $3$rd and $4$th... and then put them back to their original positions.

The hard work is left to Ayling, and the thinking is left to you! Please tell Ayling: using the operation of choosing a subsequence only once, what is the lexicographically smallest new height sequence $A'$ she can obtain?

Formal statement

Given an integer sequence $A$ of length $n$, indexed from $1$. You may choose any natural number $k$ and a subsequence $P$ of the sequence $\lang 1,2,\dots,n\rang$ with length $2k~(k\in\mathbb N)$. For all $i=1,2,\dots,k$, swap the values of $A_{P_{2i-1}}$ and $A_{P_{2i}}$. Among all possible resulting sequences $A'$, find the one with the smallest lexicographical order.

Lexicographical order: For sequences $A$ and $B$ of length $n$, we say $A$ is lexicographically smaller than $B$ if and only if:

$$\exists i\in[1,n], (\forall j\in[1,i), A_j=B_j)\land A_i<B_i.$$

Note: This problem has a special input/output method. See "Input Format" and "Output Format" for details.

Input Format

To reduce input time, the sequence $A$ will be generated inside your program using xorShift128Plus and the provided seeds. Below is a sample program in 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;
}

The input file contains only one line with four integers $n,k_1,k_2,\textit{thres}$.

The program reads the sequence length $n$, seeds $k_1,k_2$, and the upper bound $\textit{thres}$, then uses xorShift128Plus to generate $n$ random numbers consecutively, assigns each value modulo $\textit{thres}$ to $a_1,a_2,\cdots,a_n$ in order, and obtains the sequence $A$. Contestants using other languages should look up relevant information and implement the generator by themselves.

Output Format

To reduce output time, your program should output one integer on one line, representing the value of $\left(\sum_{i=1}^ni\times A_i'\right)\bmod2^{64}$.

7 20120712 21702102 4

43

10 114514 19198 10

256

Hint

Explanation for Sample #1

The generated sequence is $A=\lang 1,1,3,0,0,1,3\rang$. Choose $k=1,P=\lang 1,5\rang$, and the resulting sequence is $A'=\lang 0,1,3,0,1,1,3\rang$. Compute as required, and the answer is $43$.

Explanation for Sample #2

The generated sequence is $A=\lang 2,8,0,6,2,2,1,7,8,3\rang$. Choose $k=3,P=\lang 1,3,4,7,8,10\rang$, and the resulting sequence is $A'=\lang 0,8,2,1,2,2,6,3,8,7\rang$. Compute as required, and the answer is $256$.

Constraints and Notes

This problem uses Subtasks for scoring.

For $100\%$ of the testdata: $1\le n\le10^7$, $2\le \textit{thres}\le10^9$, $0\le k_1,k_2<2^{64}$.

For different subtasks, the following constraints apply:

Subtask ID	$n$	$\textit{thres}$	Special Property	Score
$1$	$\le10^5$	$\le10^9$	Yes	$10$
$2$	$\le20$	$\le10$	None	$15$
$3$	$\le10^7$	$=2$		$20$
$4$		$\le10^7$		$25$
$5$		$\le10^9$		$30$

• Special Property: It is guaranteed that in the correctly generated sequence $A$, there are no equal elements.

• Note: The time limit for this problem is $0.5\text s$.

• Fun fact: "The Last Singer" is sung in summer, which is clearly not during the Rainwater solar term.

Translated by ChatGPT 5