Problem Description
Professor Zhang has two sequences a1,a2,...,an and b1,b2,...,bn. He wants to perform two kinds of operations on the sequences:
- + l r x: set ai to x for all l≤i≤r.
- ? l r: find the number of i such that ai≥bi and l≤i≤r.
Input
There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:
The first line contains four integers n, m, A and B (1≤n≤105,1≤m≤3000000,1≤A,B≤216) -- the length of the sequence, the number of operations and two parameters.
The second line contains n integers a1,a2,...,an (1≤ai≤109). The third line contains n integers b1,b2,...,bn (1≤bi≤109).
As there are too many operations, the m operations are specified by parameters A and B given to the following generator routine.
int a = A, b = B, C = ~(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 (i.e. l = rnd(last) % n + 1, r = rnd(last) % n + 1, x = rnd(last) + 1). Then if l>r, you should swap their value. And at last, the i-th operation is type ?, if (l+r+x) is an even number, or type + otherwise.
Note: last is the answer of the latest type ? operation and assume last=0 at the beginning of each test case.
Output
For each test case, output an integer S=(∑i=1mi⋅zi) mod (109+7), where zi is the answer for i-the query. If the i-th query is of type +, then zi=0.
Sample Input
3
5 10 1 2
5 4 3 2 1
1 2 3 4 5
5 10 3 4
5 4 4 2 1
1 2 3 4 5
5 10 5 6
5 4 5 2 1
1 2 2 4 5
Sample Output
81
88
87
