CF1599E.Two Arrays

You are given two integer arrays of length $N$, $A1$ and $A2$. You are also given $Q$ queries of 4 types:

1 k l r x: set $Ak_i:=min(Ak_i, x)$ for each $l \leq i \leq r$.

2 k l r x: set $Ak_i:=max(Ak_i, x)$ for each $l \leq i \leq r$.

3 k l r x: set $Ak_i:=Ak_i+x$ for each $l \leq i \leq r$.

4 l r: find the $(\sum_{i=l}^r F(A1_i+A2_i)) \% (10^9+7)$ where $F(k)$ is the $k$-th Fibonacci number ($F(0)=0, F(1)=1, F(k)=F(k-1)+F(k-2)$), and $x \% y$ denotes the remainder of the division of $x$ by $y$.

You should process these queries and answer each query of the fourth type.

给你两个长度为 $N$ 的整数数组 $A1$ 和 $A2$，以及 $Q$ 个四种类型的查询：

1. 1 k l r x：对每个满足 $l \leq i \leq r$ 的下标 $i$，执行 $Ak_i := \min(Ak_i, x)$。

2. 2 k l r x：对每个满足 $l \leq i \leq r$ 的下标 $i$，执行 $Ak_i := \max(Ak_i, x)$。

3. 3 k l r x：对每个满足 $l \leq i \leq r$ 的下标 $i$，执行 $Ak_i := Ak_i + x$。

4. 4 l r：计算 $\left(\sum_{i=l}^r F(A1_i + A2_i)\right) \bmod (10^9+7)$，其中 $F(k)$ 表示第 $k$ 个斐波那契数（定义为 $F(0)=0,\ F(1)=1,\ F(k)=F(k-1)+F(k-2)$），而 $x \bmod y$ 表示 $x$ 除以 $y$ 所得的余数。

你需要依次处理所有查询，并对每个第 4 类查询输出对应答案。

The first line contains two integers $N$ and $Q$. ($1 \leq N, Q \leq 5 \times 10^4$)

The second line contains $N$ integers, array $A1_1, A1_2, \dots A1_N$. ($0 \leq A1_i \leq 10^6$)

The third line contains $N$ integers, array $A2_1, A2_2, \dots A2_N$. ($0 \leq A2_i \leq 10^6$)

The next $Q$ lines describe the queries. Each line contains 5 or 3 integers, where the first integer denotes the type of the query. ($k \in {1, 2}$, $1 \leq l \leq r \leq N$)

For queries of type 1 and 2, $0 \leq x \leq 10^9$ holds.

For queries of type 3, $−10^6 \leq x \leq 10^6$ holds.

It is guaranteed that after every query each number in arrays $A1$ and $A2$ will be nonnegative.

第一行包含两个整数 $N$ 和 $Q$。（$1 \leq N, Q \leq 5 \times 10^4$）

第二行包含 $N$ 个整数，表示数组 $A1_1, A1_2, \dots, A1_N$。（$0 \leq A1_i \leq 10^6$）

第三行包含 $N$ 个整数，表示数组 $A2_1, A2_2, \dots, A2_N$。（$0 \leq A2_i \leq 10^6$）

接下来的 $Q$ 行描述查询操作。每行包含 5 个或 3 个整数，其中第一个整数表示查询类型。（$k \in \{1, 2\}$，$1 \leq l \leq r \leq N$）

对于类型为 1 和 2 的查询，满足 $0 \leq x \leq 10^9$。

对于类型为 3 的查询，满足 $-10^6 \leq x \leq 10^6$。

保证每次查询操作后，数组 $A1$ 和 $A2$ 中的每个数均为非负数。

Print the answer to each query of the fourth type, in separate lines.

打印每个第四类查询的答案，每行一个。

In the first example: The answer for the first query is $F(1 + 2) + F(0 + 1) + F(2 + 0) = F(3) + F(1) + F(2) = 2 + 1 + 1 = 4$. After the second query, the array $A2$ changes to $[2, 4, 0]$. After the third query, the array $A1$ changes to $[0, 0, 0]$. The answer for the fourth query is $F(0 + 2) + F(0 + 4) + F(0 + 0) = F(2) + F(4) + F(0) = 1 + 3 + 0 = 4$.

In the second example: The answer for the first query is $F(1 + 4) + F(3 + 2) + F(5 + 1) = F(5) + F(5) + F(6) = 5 + 5 + 8 = 18$. The answer for the second query is $F(3 + 2) + F(5 + 1) + F(3 + 3) + F(2 + 3) = F(5) + F(6) + F(6) + F(5) = 5 + 8 + 8 + 5 = 26$. After the third query, the array $A1$ changes to $[1, 6, 6, 6, 2]$. The answer for the fourth query is $F(6 + 2) + F(6 + 1) + F(6 + 3) = F(8) + F(7) + F(9) = 21 + 13 + 34 = 68$.

在第一个例子中：第一个查询的答案为 $F(1 + 2) + F(0 + 1) + F(2 + 0) = F(3) + F(1) + F(2) = 2 + 1 + 1 = 4$。第二个查询之后，数组 $A2$ 变为 $[2, 4, 0]$。第三个查询之后，数组 $A1$ 变为 $[0, 0, 0]$。第四个查询的答案为 $F(0 + 2) + F(0 + 4) + F(0 + 0) = F(2) + F(4) + F(0) = 1 + 3 + 0 = 4$。

在第二个例子中：第一个查询的答案为 $F(1 + 4) + F(3 + 2) + F(5 + 1) = F(5) + F(5) + F(6) = 5 + 5 + 8 = 18$。第二个查询的答案为 $F(3 + 2) + F(5 + 1) + F(3 + 3) + F(2 + 3) = F(5) + F(6) + F(6) + F(5) = 5 + 8 + 8 + 5 = 26$。第三个查询之后，数组 $A1$ 变为 $[1, 6, 6, 6, 2]$。第四个查询的答案为 $F(6 + 2) + F(6 + 1) + F(6 + 3) = F(8) + F(7) + F(9) = 21 + 13 + 34 = 68$。