Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

matrices

*3200

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Two Arrays

time limit per test

5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Input

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.

Output

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

Examples

Input

3 4 1 0 2 2 1 0 4 1 3 3 2 2 2 3 1 1 1 3 0 4 1 3

Output

4 4

Input

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

Output

18 26 68

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/25/2024 11:46:17 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|