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}\}$. Here, each $p_{i}$ can only be $+$ or $\times$.

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

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

calculated according to the standard order of operations.

An example of the calculation 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 query the weight of a given interval.

You need to maintain the following 3 operations:

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

Operation 2: Given $l, r, y$, change all $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

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}, \ldots, p_{n-1}$, where $0$ represents $+$ and $1$ represents $\times$.

The next $m$ lines each contain an operation.

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

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

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

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

Output

For each operation 3, output one integer on a new line representing the answer.

Examples

Input 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 1

205
134
45058
3465

Note

Explanation 1

The initial two sequences and the first two operations are the same as in the problem description. 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 $$

Input 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 2

900803889
834560968
247321621
852589651
564942769
525160717
564942769
719106438

Constraints and Data Range

Idea: Juan_feng.

Solution: nzhtl1477, ccz181078.

Code: Juan_feng, nzhtl1477, rehtorbegnaro, ccz181078.

Data: Juan_feng, nzhtl1477, rehtorbegnaro.