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.

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.

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 $ .