Zhang 教授有两个序列 $a_1, a_2, \dots, a_n$ 和 $b_1, b_2, \dots, 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$ 的个数。

输入格式

输入包含多组测试数据。第一行包含一个整数 $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, \dots, a_n$ ($1 \le a_i \le 10^9$)。第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^9$)。

由于操作次数可能非常大，这 $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) \pmod n + 1, r = \text{rnd}(last) \pmod n + 1, x = \text{rnd}(last) + 1$）。然后，如果 $l > r$，则交换它们的值。最后，如果 $(l + r + x)$ 是偶数，则第 $i$ 次操作类型为 ?，否则类型为 +。

注意：$last$ 是最近一次 ? 操作的答案。假设每组测试数据开始时 $last = 0$。

最多有 300 组测试数据，输入文件总大小不超过 8 MB。

输出格式

对于每组测试数据，输出整数 $S = \left(\sum_{i=1}^{m} i \cdot z_i\right) \pmod{10^9 + 7}$，其中 $z_i$ 是第 $i$ 次查询的答案。如果第 $i$ 次查询是 + 类型，则假设 $z_i = 0$。

样例

输入 1

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

输出 1

81
88
87