Background

Chimuzu messed up badly in the first round of the NOI Qualifier, getting two big zeros, so he went back to study cultural classes.

He dug out a basic four-operations arithmetic practice problem... and then found that he could not do it.

So he needs your help. As a reward, he will give you $100$ points.

Advertisement at the top: would anyone like to take a look at the fusion tree I wrote?

(Actually, I also wrote about the Brodal queue.)

Problem Description

Chimuzu has a number sequence $\{a_{1},a_{2},\ldots,a_{n}\}$ and an operator sequence $\{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 obtained by writing the string

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

and then evaluating it according to operator precedence.

An example is given below:

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 two sequences and also query the weight of a given interval.

You need to maintain these $3$ operations:

Operation 1: given $l,r,x$, set $a_{l},a_{l+1},\ldots,a_{r}$ all to $x$.

Operation 2: given $l,r,y$, set $p_{l},p_{l+1},\ldots,p_{r}$ all to $y$, where $0$ means $+$ and $1$ means $\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$ means $+$ and $1$ means $\times$.

Then follow $m$ lines, each describing one operation.

Each operation starts with an identifier $op$, indicating the operation type, followed by the parameters as described above.

When $op=1$, input $3$ integers $l,r,x$, meaning to set $a_{l},a_{l+1},\ldots,a_{r}$ all to $x$.

When $op=2$, input $3$ integers $l,r,y$, meaning to set $p_{l},p_{l+1},\ldots,p_{r}$ all to $y$, where $0$ means $+$ and $1$ means $\times$.

When $op=3$, input $2$ integers $l,r$, meaning 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 required answer.

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

205
134
45058
3465

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

900803889
834560968
247321621
852589651
564942769
525160717
564942769
719106438

Hint

Sample Explanation 1

The initial two sequences and the first two operations are the example in the statement. After the fourth operation, the two 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$$

Constraints and Notes

For $1\%$ of the testdata, it is Sample 1, and the time limit is 1.5s.

For another $14\%$ of the testdata, $n,m\leq 1000$, and the time limit is 1.5s.

For another $5\%$ of the testdata, there are no modification operations, and the time limit is 1.5s.

For another $14\%$ of the testdata, the testdata is guaranteed to be random, and the time limit is 1.5s.

For another $19\%$ of the testdata, there is no operation 1, and the time limit is 1.5s.

For another $19\%$ of the testdata, there is no operation 2, and the time limit is 1.5s.

For another $8\%$ of the testdata, the time limit is 5s.

For another $10\%$ of the testdata, the time limit is 3s.

For $100\%$ of the testdata, $n,m\leq 100000$, $1\leq a_{i},x\lt 2^{32}$, and both $a_{i}$ and $x$ are odd, $p_{i},y\in\{0,1\}$, $1\leq l\leq r\leq n$. Also, for all operations $2$, it additionally holds that $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.

Translated by ChatGPT 5