407498: GYM102803 B Bills of Paradise
Description
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.
InputThe 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$$$.
OutputFor each command $$$\texttt{F}$$$ and command $$$\texttt{C}$$$, output a line containing the answer.
ExampleInput8 1234567890987 654321234567 8 F 234567891234 D 345678912345 C 456789123456 R 567891234567 C 100000000000 D 100000000000 C 654321234567 F 987654321234Output
245682167348 680270154870 0 1552964262449 1000000000000Note
For this example, the generated sequence is $$$\lbrace 565040138009, 102855093402, 245682167348, 331732894120, 987193824410, 699419056191, 780922390772, 410509062972 \rbrace$$$