题目描述
Chimuzu 手上有一个数字序列 $\{a_{1},a_{2},\ldots,a_{n}\}$ 和一个运算符序列 $\{p_{1},p_{2},\ldots,p_{n-1}\}$。其中 $p_{i}$ 只能为 $+$ 或 $\times$。
我们定义一个区间 $[l,r]$ 的权值 $w(l,r)$ 为将字符串
$$ a_{l}~p_{l}~a_{l+1}~p_{l+1} \cdots a_{r-1}~p_{r-1}~a_{r} $$
写下来之后，按照运算符的优先级计算出的结果。
下面给出一个运算的例子：
若 $a=\{1,3,5,7,9,11\}$，$p=\{+,\times,\times,+,\times\}$，那么有：
$$ w(1,6)=1+3\times 5\times 7+9\times 11=205 $$
$$ w(3,6)=5\times 7+9\times 11=134 $$
Chimuzu 需要你对这两个序列进行修改，同时查询某个给定区间的权值。
你需要维护这 $3$ 个操作：
操作一：给定 $l,r,x$，将 $a_{l},a_{l+1},\ldots,a_{r}$ 全部修改成 $x$。
操作二：给定 $l,r,y$：将 $p_{l},p_{l+1},\ldots,p_{r}$ 全部修改成 $y$，$0$ 表示 $+$，$1$ 表示 $\times$。
操作三：给定 $l,r$：查询 $w(l,r) \bmod 1000000007$ 的值。
输入格式
第一行包含两个整数 $n,m$。
第二行包含 $n$ 个整数 $a_{1},a_{2},\ldots,a_{n}$。
第三行包含 $n-1$ 个整数 $p_{1},p_{2},\cdots,p_{n-1}$，$0$ 表示 $+$， $1$ 表示 $\times$。
接下来 $m$ 行，每行有一个操作。
一开始输入一个标识符 $op$，表示操作类型，接着按照题目描述输入各操作的参数。
$op=1$ 时，输入 $3$ 个整数 $l,r,x$，表示将 $a_{l},a_{l+1},\ldots,a_{r}$ 全部修改成 $x$。
$op=2$ 时，输入 $3$ 个整数 $l,r,y$，表示将 $p_{l},p_{l+1},\ldots,p_{r}$ 全部修改成 $y$，$0$ 表示 $+$，$1$ 表示 $\times$。
$op=3$ 时，输入 $2$ 个整数 $l,r$，表示查询 $w(l,r) \bmod 1000000007$ 的值。
输出格式
对于每一次操作 $3$，输出 $1$ 行 $1$ 个整数表示所求答案。
样例 #1
样例输入 #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
样例输出 #1
205 134 45058 3465
样例 #2
样例输入 #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
样例输出 #2
900803889 834560968 247321621 852589651 564942769 525160717 564942769 719106438
提示
样例解释 1
初始的两个序列和前两次操作是题目描述中的例子。第四次操作结束后，两个序列变成了如下形态
$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 $$
数据范围与约定
对于其中 $1\%$ 的数据，为样例 1，时限为 1.5s
对于另外 $14\%$的数据，$n,m\leq 1000$ ，时限为 1.5s
对于另外 $5\%$ 的数据，没有修改操作，时限为 1.5s
对于另外 $14\%$ 的数据，数据保证随机，时限为 1.5s
对于另外 $19\%$ 的数据，没有 1 操作，时限为 1.5s
对于另外 $19\%$ 的数据，没有 2 操作，时限为 1.5s
对于另外 $8\%$ 的数据，时限为 5s
对于另外 $10\%$ 的数据，时限为 3s
对于 $100\%$ 的数据，$n,m\leq 100000$，$1\leq a_{i},x\lt 2^{32}$，$a_{i},x$ 均为奇数，$p_{i},y\in\{0,1\}$，$1\leq l\leq r\leq n$，所有操作 $2$ 还满足 $r\lt n$。时限为 1.5s
Idea：Juan_feng。
Solution：nzhtl1477，ccz181078。
Code：Juan_feng，nzhtl1477，rehtorbegnaro，ccz181078。
Data：Juan_feng，nzhtl1477，rehtorbegnaro。