Problem Description

Warm spring sunshine shines on the earth, and this is the happiest time for the little animals on the grassland. The little animals held a ball on the grassland to celebrate this wonderful time.

The most important part of the ball is dancing in circles. $n$ little animals hold hands and form a big circle, dancing with the music. During the dance, the animals may change their formation. Their way of changing is: animal A lets go of its right hand, animal B lets go of its left hand, then animal A and B hold hands, and the two hands that were released correspondingly (if any) also hold hands.

For example, suppose there are $10$ little animals forming a circle in order. The right hand of animal $1$ holds the left hand of animal $2$, the right hand of animal $2$ holds the left hand of animal $3$, and so on. Finally, the right hand of animal $10$ holds the left hand of animal $1$. If the formation is changed through animals $2$ and $8$, then the right hand of animal $2$ holds the left hand of animal $8$, and correspondingly the left hand of animal $3$ holds the right hand of animal $7$, forming two circles 1-2-8-9-10 and 3-4-5-6-7. If now the formation is changed through animals $2$ and $6$, then one big circle 1-2-6-7-3-4-5-8-9-10 will be formed. Note that if at this time the formation is changed through animals $1$ and $2$, then the formation will not change, because after the right hand of animal $1$ and the left hand of animal $2$ are released, they are held together again.

During the dance, each animal $i$ has a happiness value $H_i$ and a moving value $F_i$.

If two animals are in the same circle, their happiness values will affect each other and produce happiness energy. If two animals $i, j(i\neq j)$ are in the same circle of size $t$, and animal $i$ is at the $p$-th position to the right of animal $j$ (the $1$-st position to the right of animal $j$ is the animal held by the right hand of animal $j$, and the $2$-nd position is the animal held by the right hand of the animal at the $1$-st position, and so on), then the happiness energy produced is $(t-p)\times H_j\times F_i$. During the dance, the animals’ happiness values and moving values may change.

At the beginning of the dance, all animals form one circle in increasing order of their indices, and the animal at the $i$-th position to the right of animal $n$ is exactly animal $i$. Now, given the process of formation changes and the process of changes in happiness values and moving values, find the sum of the happiness energy produced by all animals after each formation change.

Constraints

Input Format

The first line contains an integer $n$, representing the number of animals.

In the next $n$ lines, each line contains two integers $H_i$ and $F_i$ separated by a space, giving the happiness value and moving value of each animal in order of indices.

The next line contains an integer $m$, representing the number of changes of formation, happiness values, and moving values.

In the next $m$ lines, each line contains three integers $k$, $p$, and $q$ separated by spaces. When $k=1$, it means the animals changed formation through animal $p$ and animal $q$. When $k=2$, it means the happiness value of animal $p$ becomes $q$. When $k=3$, it means the moving value of animal $p$ becomes $q$.

Output Format

Output $m$ lines. Each line contains one integer, representing the sum of energy produced by all animals after each change.

The answer may be very large. You need to output the remainder of the answer modulo $1000000007$ (i.e. $10^9+7$).

10
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
9
1 2 8
1 2 6
2 8 10
3 5 10
1 1 2
1 2 1
2 5 5
1 4 8
1 4 5

100
450
855
1341
1341
811
923
338
923

Hint

For $20\%$ of the testdata, $2\le n,m\le100$.

For $30\%$ of the testdata, $2\le n,m\le1000$.

For another $20\%$ of the testdata, there are only operations with $k=1$, and both $H_i$ and $F_i$ are $1$.

For another $20\%$ of the testdata, there are only operations with $k=1$ or $2$, and all $F_i$ are $1$.

For $100\%$ of the testdata, $2\le n,m\le10^5$, $0\le H_i,F_i\le10^9$, $1\le k\le3$. When $k=1$, $1\le p,q\le n$ and $p\neq q$. When $k=2$ or $3$, $1\le p\le n$ and $0\le q\le10^9$.

Translated by ChatGPT 5