407498: GYM102803 B Bills of Paradise

Little Y lost the racing game and signed his name on the contract. He has to pay for $$$n$$$ bills! And the $$$i$$$-th bill is of $$$a_i$$$ dollars.

However, the owner of contract was devil. The owner rolled eyes and gave him a random number generator with given random seeds denoted by two integers $$$k_1$$$ and $$$k_2$$$ to get the sequence of $$$a_i$$$. The following code in C++ tells you how to generate the sequence. You can use the code directly in your submissions.

unsigned long long k1, k2;

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;
}

int n;
long long a[1000001];

void gen() {
    scanf("%d %llu %llu", &n, &k1, &k2);
    for (int i = 1; i <= n; i++) {
        a[i] = xorShift128Plus() % 999999999999 + 1;
    }
}

$$$Q$$$ commands are sent from the owner. There are four types of commands.

• $$$\texttt{F} ~ x$$$: Query the smallest unpaid bill $$$a_i$$$ where $$$a_i \ge x$$$ holds. If such $$$a_i$$$ doesn't exist, print $$$10^{12}$$$.
• $$$\texttt{D} ~ x$$$: Pay the smallest unpaid bill $$$a_i$$$ where $$$a_i \ge x$$$ holds. If such $$$a_i$$$ doesn't exist, do nothing.
• $$$\texttt{C} ~ x$$$: Query the summation of all unpaid bills $$$a_i$$$ where $$$a_i \le x$$$ holds. If such $$$a_i$$$ doesn't exist, print $$$0$$$.
• $$$\texttt{R} ~ x$$$: Refund (退款) all paid bills $$$a_i$$$ and mark them unpaid where $$$a_i \le x$$$ holds. If such $$$a_i$$$ doesn't exist, do nothing.

You are required to process these commands now.

The first line contains integers $$$n, k_1, k_2 ~ (1 \le n \le 10^6, 0 \le k_1, k_2 \le 2^{64}-1)$$$, which is used in function $$$\texttt{gen()}$$$.

The second line contains integer $$$Q ~ (1 \leq Q \leq 5 \cdot 10^5)$$$.

Then follow $$$Q$$$ lines, each containing one command $$$op ~ x ~~ (op \in \lbrace \texttt{F}, \texttt{D}, \texttt{C}, \texttt{R} \rbrace, 1 \leq x \leq 10^{12}-1)$$$.

It is guaranteed that the count of type $$$\texttt{R}$$$ does not exceed $$$10$$$, and $$$a_i \neq a_j$$$ holds for each pair of $$$(i, j)$$$ where $$$i \neq j$$$.

For each command $$$\texttt{F}$$$ and command $$$\texttt{C}$$$, output a line containing the answer.

8 1234567890987 654321234567
8
F 234567891234
D 345678912345
C 456789123456
R 567891234567
C 100000000000
D 100000000000
C 654321234567
F 987654321234

245682167348
680270154870
0
1552964262449
1000000000000

For this example, the generated sequence is $$$\lbrace 565040138009, 102855093402, 245682167348, 331732894120, 987193824410, 699419056191, 780922390772, 410509062972 \rbrace$$$