Buses from Bragadiru

Bragadiru, a city on the outskirts of Bucharest, has just revamped its bus network! Before leaving for Piatra Neamț, Andrei has to take the bus from his station to another stop, where he will meet another Andrei (from the legendary team Andrei of 2024). He observed that the city hall has imposed a new pricing model for the buses:

• Each stop $i$ has two associated costs: $depart_i$, the price to leave from station $i$, and $arrive_i$, the price to arrive at station $i$.
• Traveling directly from station $i$ to station $j$ costs $C(i, j) = depart_i \cdot arrive_j$ lei.
• A bus trip is a sequence of stops $X_0, X_1, \ldots, X_k$ where each consecutive pair is connected by a direct hop (stops may repeat). Its length is $k$ -- the number of hops -- and its total cost is the product $C(X_0, X_1) \cdot C(X_1, X_2) \cdots C(X_{k-1}, X_k)$ lei.

Task

Andrei watches a stream of $Q$ events. Some are pricing adjustments published by the city hall (the prices change in real time); others are questions Andrei asks about the network in its current state. Each event has one of the following forms:

• $\text{1 L R val}$ -- (pricing update) $depart_i \gets depart_i + val$ for all $L \leq i \leq R$.
• $\text{2 L R val}$ --(pricing update) $arrive_i \gets arrive_i + val$ for all $L \leq i \leq R$.
• $\text{3 L R k}$ -- (query) Restrict the network to only the stops in the interval $[L, R]$. Compute the sum of total costs of all trips of length exactly $k$ whose stops lie entirely within $[L, R]$.

Since the answer to a query can be very large, output it modulo $10^9 + 7$.

Input data

The first line of the input contains an integer $N$, representing the number of bus stops in Bragadiru.

The second line contains $N$ space-separated integers, $depart_1, depart_2, \ldots, depart_N$, representing the cost to depart from each stop.

The third line contains $N$ space-separated integers, $arrive_1, arrive_2, \ldots, arrive_N$, representing the cost to arrive at each stop.

The fourth line contains an integer $Q$, representing the number of events.

The following $Q$ lines describe the events. Each line begins with an integer $type \in \{1, 2, 3\}$, followed by additional space-separated integers corresponding to the parameters described above.

Output data

For each query event (type $3$), output on a separate line the requested sum, taken modulo $10^9 + 7$.

Constraints and clarifications

• $1 \leq N, Q \leq 100 \ 000$
• $1 \leq arrive_i, depart_i \leq 10 \ 000$ for all $1 \leq i \leq N$.
• $1 \leq L \leq R \leq N$ for every event.
• $1 \leq val \leq 10 \ 000$ for every event of type 1 or 2.
• $1 \leq k \leq 10^9$ for every event of type 3.

Example

stdin

3
2 3 1
1 2 4
4
3 1 3 1
1 2 2 5
3 1 3 1
3 2 3 2

stdout

42
77
1080

Explanation

Initially $depart = [2, 3, 1]$ and $arrive = [1, 2, 4]$.

• $\text{3 1 3 1}$: query on $[1, 3]$ with $k = 1$. Each trip has a single hop $i \to j$ for $i, j \in \{1, 2, 3\}$, with cost $depart_i \cdot arrive_j$. Summing over all $9$ pairs gives $42$.
• $\text{1 2 2 5}$: update -- $depart_2$ becomes $3 + 5 = 8$, so $depart = [2, 8, 1]$.
• $\text{3 1 3 1}$: same kind of query, now $(2 + 8 + 1) \cdot (1 + 2 + 4) = 11 \cdot 7 = 77$.
• $\text{3 2 3 2}$: query on $[2, 3]$ with $k = 2$. A trip of length $2$ visits a sequence of three stops $X_0 \to X_1 \to X_2$, each in $\{2, 3\}$, and

stops may repeat -- e.g. $2 \to 2 \to 2$ or $3 \to 3 \to 2$ are perfectly valid trips. So there are $2^3 = 8$ trips in total, not just the ones that use distinct stops.

With $depart = [2, 8, 1]$ and $arrive = [1, 2, 4]$, the four edge costs within $\{2, 3\}$ are

Each trip's cost is the product of its two edges:

Their sum is $256 + 512 + 64 + 128 + 32 + 64 + 8 + 16 = 1080$.