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() {
$\quad$unsigned long long k3 = k1, k4 = k2;
$\quad$k1 = k4;
$\quad$k3 ^= k3 << 23;
$\quad$k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
$\quad$return k2 + k4;
}

int n;
long long a[1000001];

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


$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 one integer T (1 ≤ T ≤ 5) denoting the count of testcase.

For each testcase,

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

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

Then follow Q lines, each containing one command op x (op ∈{F,D,C,R},1 ≤ x ≤ $10^{12}$ -1).

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

It is guaranteed that $\sum$n ≤ $3.2\times 10^6$ and $Q ≤ 1.7\times 10^6$.

For each command F and command C, output a line containing the answer.

1
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 {565040138009,102855093402,245682167348,331732894120,987193824410,699419056191,780922390772,
410509062972}

“红旗杯”第十五届黑龙江省大学生程序设计竞赛