Range Expression Evaluation with Updates

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}\}\), where each \(p_i\) is either \( + \) or \( \times \) (with the input representation \(0\) for \( + \) and \(1\) for \( \times \)). For any interval \([l,r]\), define its weight \(w(l,r)\) as follows:

Write down the expression \[ a_{l}\; p_{l}\; a_{l+1}\; p_{l+1}\; \cdots \; p_{r-1}\; a_r \] and evaluate it using the usual operator precedence (multiplication before addition). Equivalently, the expression is computed by summing up the products of maximal consecutive segments connected by multiplication, with plus signs acting as separators.

For example, 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 support the following three operations on these sequences:

• Operation 1: Given \(l, r, x\), update \(a_l, a_{l+1}, \ldots, a_r\) to \(x\).
• Operation 2: Given \(l, r, y\), update \(p_l, p_{l+1}, \ldots, p_r\) to \(y\) (where \(y=0\) represents \( + \) and \(y=1\) represents \( \times \)).
• Operation 3: Given \(l, r\), output \(w(l,r) \bmod 1000000007\).

Note: The expression is always evaluated by applying multiplication before addition.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) --- the number of numbers in the sequence and the number of operations, respectively.

The second line contains \(n\) space-separated integers: \(a_1, a_2, \ldots, a_n\).

The third line contains \(n-1\) space-separated integers, each equal to either \(0\) (representing \( + \)) or \(1\) (representing \( \times \)), denoting the operator sequence \(p_1, p_2, \ldots, p_{n-1}\).

Each of the next \(m\) lines represents an operation in one of the following formats:

• If the line begins with 1, it is followed by three integers \(l\), \(r\), and \(x\) indicating that for all indices from \(l\) to \(r\), \(a_i\) should be set to \(x\).
• If the line begins with 2, it is followed by three integers \(l\), \(r\), and \(y\) indicating that for all indices from \(l\) to \(r\), \(p_i\) should be set to \(y\) (with \(0\) for \( + \) and \(1\) for \( \times \)).
• If the line begins with 3, it is followed by two integers \(l\) and \(r\); you need to compute and output \(w(l,r) \bmod 1000000007\) for that interval.

outputFormat

For each operation of type 3, output the resulting value on a separate line.

sample

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

205
134
1100
210

</p>