Differencia

Professor Zhang has two sequences $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_n$. He wants to perform two kinds of operations on the sequences:

• "+ $l$ $r$ $x$": set $a_i$ to $x$ for all $l \le i \le r$.
• "? $l$ $r$": find the number of $i$ such that $a_i \ge b_i$ and $l \le i \le r$.

The number of operations can be large, so the $m$ operations are specified by parameters $A$ and $B$ given to the following generator routine.

int a = A, b = B, C =  (1<<31), M = (1<<16)-1;
int rnd(int last) {
  a = (36969 + (last >> 3)) * (a & M) + (a >> 16);
  b = (18000 + (last >> 3)) * (b & M) + (b >> 16);
  return (C & ((a << 16) + b)) % 1000000000;
}

For the $i$-th operation, first call rnd(last) three times to get $l$, $r$ and $x$: $l = \text{rnd}(last) \bmod n + 1$, $r = \text{rnd}(last) \bmod n + 1$, $x = \text{rnd}(last) + 1$. If $l > r$, swap them. The operation is of type "?" if $l + r + x$ is even, and of type "+" otherwise. Here $last$ is the answer of the most recent "?" operation, and $last = 0$ at the beginning of each test case.

There are multiple test cases. The first line contains an integer $T$, the number of test cases. For each test case, the first line contains four integers $n$, $m$, $A$ and $B$ ($1 \le n \le 10^{5}$, $1 \le m \le 3\,000\,000$, $1 \le A, B \le 2^{16}$). The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^{9}$). The third line contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 10^{9}$).

There are at most $300$ test cases, and the total input size is at most $8$ mebibytes.

For each test case, output the integer $S = \left(\sum_{i=1}^{m} i \cdot z_i\right) \bmod (10^9 + 7)$, where $z_i$ is the answer to the $i$-th query. If the $i$-th operation is of type "+", then $z_i = 0$.