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

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

`Update(l, r, x)`

- set through to all be equal to .`Query(l, r)`

- compute the number of indices where and .

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

In tests worth 1 mark, .

In tests worth an additional 2 marks, .

In tests worth an additional 4 marks, .

#### Input Specification

The first line contains four integers, , , , and .

The second line contains integers, the sequence .

The third line contains integers, the sequence .

Because the number of operations is large, you'll be generating the 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 th operation, call `rnd`

three times, setting to be `rnd(last) % n + 1`

, then to be `rnd(last) % n + 1`

, then to be `rnd(last) + 1`

. If , then swap them. if is even, the 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 be if the th operation was an `Update`

, and the result of the `Query`

operation otherwise. Output modulo `998244353`

.

#### Sample Input

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

#### Sample Output

`87`

## Comments