Problem Background

Chimuzu failed in the first round of the provincial selection and had to go back to studying cultural courses.

He found a basic arithmetic practice problem... and realized he couldn't solve it.

So he needs your help, and in return, he will give you 100 points.

(By the way, check out my Fusion Tree and Brodal queue)

Problem Description

Chimuzu has a sequence of numbers $\{a_{1},a_{2},\ldots,a_{n}\}$ and a sequence of operators $\{p_{1},p_{2},\ldots,p_{n-1}\}$. Each $p_{i}$ can only be $+$ or $\times$.

We define the weight $w(l,r)$ of an interval $[l,r]$ as the result of evaluating the string

$$ a_{l}~p_{l}~a_{l+1}~p_{l+1} \cdots a_{r-1}~p_{r-1}~a_{r} $$

according to the precedence of operators.

Here is an example of an operation:

If $a=\{1,3,5,7,9,11\}$ and $p=\{+,\times,\times,+,\times\}$, then:

$$ w(1,6)=1+3\times 5\times 7+9\times 11=205 $$

$$ w(3,6)=5\times 7+9\times 11=134 $$

Chimuzu needs you to modify these sequences and query the weight of a given interval.

You need to maintain these 3 operations:

Operation 1: Given $l,r,x$, change $a_{l},a_{l+1},\ldots,a_{r}$ to $x$.

Operation 2: Given $l,r,y$, change $p_{l},p_{l+1},\ldots,p_{r}$ to $y$, where $0$ represents $+$ and $1$ represents $\times$.

Operation 3: Given $l,r$, query the value of $w(l,r) \bmod 1000000007$.

Input Format

The first line contains two integers $n,m$.

The second line contains $n$ integers $a_{1},a_{2},\ldots,a_{n}$.

The third line contains $n-1$ integers $p_{1},p_{2},\cdots,p_{n-1}$, where $0$ represents $+$ and $1$ represents $\times$.

The next $m$ lines, each describing an operation.

The first input is an identifier $op$, indicating the type of operation, followed by the parameters for each operation as described in the problem.

For $op=1$, input 3 integers $l,r,x$, indicating to change $a_{l},a_{l+1},\ldots,a_{r}$ to $x$.

For $op=2$, input 3 integers $l,r,y$, indicating to change $p_{l},p_{l+1},\ldots,p_{r}$ to $y$, where $0$ represents $+$ and $1$ represents $\times$.

For $op=3$, input 2 integers $l,r$, indicating to query the value of $w(l,r) \bmod 1000000007$.

Output Format

For each operation 3, output 1 line containing 1 integer, which is the requested answer.

Sample Input and Output

Input Sample #1

6 6
1 3 5 7 9 11
0 1 1 0 1
3 1 6
3 3 6
1 1 2 13
2 3 4 1
3 1 6
3 3 6

Output Sample #1

205
134
45058
3465

Input Sample #2

20 20
525160717 947806001 1495853547 5283947 39115023 1008063001 397093019 1434942997 247321621 145181297 359967329 642658073 1402873249 50886569 150383317 1004954721 351661441 1660759179 48867601 1316622161 
0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 
3 2 19
3 2 15
3 9 9
1 16 16 394339135
2 1 19 0
3 1 15
1 4 11 564942769
3 7 7
2 2 19 0
3 1 1
3 9 9
1 9 9 705415201
1 3 18 152081579
1 13 17 905666497
1 11 17 612267547
1 2 20 111949431
2 1 1 0
1 10 17 838945201
2 4 18 0
3 2 18

Output Sample #2

900803889
834560968
247321621
852589651
564942769
525160717
564942769
719106438

Notes

Sample Explanation 1

The initial sequences and the first two operations are from the problem description. After the fourth operation, the sequences become:

$a=\{13,13,5,7,9,11\}$, $p=\{+,\times,\times,\times,\times\}$

$$ w(1,6)=13+13\times 5\times 7\times 9\times 11=45058 $$

$$ w(3,6)=5\times 7\times 9\times 11=3465 $$

Data Range and Constraints

For 1% of the data, it is Sample 1 with a time limit of 1.5s.

For another 14% of the data, $n,m\leq 1000$ with a time limit of 1.5s.

For another 5% of the data, there are no modification operations with a time limit of 1.5s.

For another 14% of the data, the data is guaranteed to be random with a time limit of 1.5s.

For another 19% of the data, there are no operation 1s with a time limit of 1.5s.

For another 19% of the data, there are no operation 2s with a time limit of 1.5s.

For another 8% of the data, the time limit is 5s.

For another 10% of the data, the time limit is 3s.

For 100% of the data, $n,m\leq 100000$, $1\leq a_{i},x\lt 2^{32}$, $a_{i},x$ are odd numbers, $p_{i},y\in\{0,1\}$, $1\leq l\leq r\leq n$, and all operation 2s also satisfy $r\lt n$. The time limit is 1.5s.

Idea: Juan_feng.

Solution: nzhtl1477, ccz181078.

Code: Juan_feng, nzhtl1477, rehtorbegnaro, ccz181078.

Data: Juan_feng, nzhtl1477, rehtorbegnaro.

见题面 Input 部分

见题面 Output 部分