Differencia

Zhang 교수는 길이가 $n$인 두 수열 $a_1, a_2, \ldots, a_n$과 $b_1, b_2, \ldots, b_n$을 가지고 있다. 그는 이 수열에 두 종류의 연산을 수행하려고 한다.

• "+ $l$ $r$ $x$": 모든 $l \le i \le r$인 $a_i$를 $x$로 바꾼다.
• "? $l$ $r$": $a_i \ge b_i$이고 $l \le i \le r$인 $i$의 개수를 구한다.

연산 횟수가 매우 클 수 있으므로, $m$개의 연산은 매개변수 $A$와 $B$를 아래 생성기 루틴에 넣어 지정한다.

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

$i$번째 연산에서는 먼저 rnd(last)를 세 번 호출해 $l$, $r$, $x$를 얻는다. $l = \text{rnd}(last) \bmod n + 1$, $r = \text{rnd}(last) \bmod n + 1$, $x = \text{rnd}(last) + 1$이다. $l > r$이면 두 값을 서로 바꾼다. $l + r + x$가 짝수이면 "?" 연산, 홀수이면 "+" 연산이다. 여기서 $last$는 가장 최근 "?" 연산의 답이며, 각 테스트 케이스가 시작될 때 $last = 0$이다.

테스트 케이스가 여러 개 주어진다. 첫 줄에는 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫 줄에는 네 정수 $n$, $m$, $A$, $B$ ($1 \le n \le 10^{5}$, $1 \le m \le 3\,000\,000$, $1 \le A, B \le 2^{16}$)가 주어진다. 둘째 줄에는 $n$개의 정수 $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^{9}$)이, 셋째 줄에는 $n$개의 정수 $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 10^{9}$)이 주어진다.

테스트 케이스는 최대 $300$개이며, 전체 입력 크기는 최대 $8$ MiB이다.

각 테스트 케이스마다 정수 $S = \left(\sum_{i=1}^{m} i \cdot z_i\right) \bmod (10^9 + 7)$을 출력한다. 여기서 $z_i$는 $i$번째 "?" 질의의 답이다. $i$번째 연산이 "+" 연산이면 $z_i = 0$이다.