Problem Description

This is a simple data structure problem.

In this problem, you need to maintain a sequence of numbers. Each position of the sequence has two parameters $a$ and $b$.

Now there are $m$ operations, and these operations can be divided into four types.

Type 1: Given interval $(l, r)$ and $x$, and mark 0/1 represents $a$ parameter or $b$ parameter, for each position in the interval, add $x$ to the $a$ parameter or $b$ parameter at this position.

Type 2: Given interval $(l, r)$, for each position in the interval, the $a$ parameter of this position becomes $3a+2b$, and the $b$ parameter becomes $3a-2b$.For example, originally $a=1$, $b=2$, after the operation becomes $a=7$, $b=-1$.

Type 3: Given interval $(l, r)$, for each position in the interval, exchange the two parameters $a$, $b$ corresponding to this position.

Type 4: Given interval $(l,r)$, query$\sum_{i=l}^ra_i*b_i$

This question is very simple, can you finish it?

Input

There is only one test case for this question.

In the first line, a positive integer $n$ ($n \leq 200000$) represents the length of the sequence.

In the next $n$ lines, the i-th line have two numbers in each line to represent the two parameters $a_i$ and $b_i$($1 \leq a_i,b_i \leq 1000000000$) at each position

In the next line, a positive integer $q$ ($q \leq 200000$) represents the number of operations.

For the next $q$ lines

$1$ $tag$ $l$ $r$ $x$($0 \leq tag \leq 1,1 \leq x \leq 1000000000$)means $a$ or $b$ plus $x$ in every position of this interval

$2$ $l$ $r$ Let $a$ become $3a+2b$ and $b$ become $3a-2b$ in every position of this interval

$3$ $l$ $r$ exchange the weight of $a$ and $b$ in every position of this interval

$4$ $l$ $r$ Query the sum of value of $a*b$ in every position of this interval

Output

For each type $4$ query, output a line of a positive integer to represent the result of the query, and the answer is modulo $1000000007$.

5
1 4
3 2
4 1
3 6
7 3
6
1 0 2 4 2
2 2 4
4 1 4
3 3 5
1 1 4 5 3
4 1 4

614
623