Mock CCC wouldn't be a real mock CCC without a data structures problem, would it?

You're given two sequences of $N$ integers $a$ and $b$, and you need to support two operations:

• Update(l, r, x) - set $a_l$ through $a_r$ to all be equal to $x$.
• Query(l, r) - compute the number of indices $i$ where $l\le i\le r$ and $a_i\ge b_i$.

DMOJ has been having some issues with test data taking up too much space, so you're going to generate the operations and solve the problem for us!

Constraints

$1\le N\le {10}^5$

$1\le M\le 3\cdot {10}^6$

$1\le A,B\le 2^{16}$

$1\le a_i,b_i\le {10}^9$

In tests worth 1 mark, $M\le 50$.

In tests worth an additional 2 marks, $M\le {10}^6$.

In tests worth an additional 4 marks, $M\le 2\cdot {10}^6$.

Input Specification

The first line contains four integers, $N$, $M$, $A$, and $B$.

The second line contains $N$ integers, the sequence $a$.

The third line contains $N$ integers, the sequence $b$.

Because the number of operations is large, you'll be generating the $m$ operations using the following code.

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

The intended solution does not exploit the random number generation used; it would work even if the operations were hand-constructed.

For the $i$th operation, call rnd three times, setting $l$ to be rnd(last) % n + 1, then $r$ to be rnd(last) % n + 1, then $x$ to be rnd(last) + 1. If $l>r$, then swap them. if $l+r+x$ is even, the $i$th operation is Query(l, r). Otherwise, it is Update(l, r, x).

last is always the last return value of Query. last starts out being 0.

Output Specification

Let $v_i$ be $0$ if the $i$th operation was an Update, and the result of the Query operation otherwise. Output $${\displaystyle \sum _{i=1}^{m}i\cdot v_i}$$ modulo 998244353.

Sample Input

5 10 5 6
5 4 5 2 1
1 2 2 4 5

Sample Output

87