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?

Format

Input

There is only one test case for this question.

In the first line, a positive integer n $(n \leqslant 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 \leqslant a_i,b_i \leqslant 1000000000)$ at each position

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

For the next q lines

1 tag l r x $(0 \leqslant tag \leqslant 1,1 \leqslant x \leqslant 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.

Samples

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