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.
Output
Print the answer to each query of the fourth type, in separate lines.
Note
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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
1 0 2
2 1 0
4 1 3
3 2 2 2 3
1 1 1 3 0
4 1 3
|
4
4
|
|
2
|
5 4
1 3 5 3 2
4 2 1 3 3
4 1 3
4 2 5
2 1 2 4 6
4 2 4
|
18
26
68
|