Selling horses

Time limit2sMemory limit512 MB

Summary

One horse multiplies by X[i] each year and any held horses sell at price Y[i]; report the maximum revenue after each point update modulo 1e9+7.

Level: Hard8 of 10
Topics: Segment tree, Greedy, Math
Solved: No attempts yet

Problem

Mansur raises horses. Today he owns more horses than anyone else in Kazakhstan, but $N$ years ago he was a young man with a single horse.

Number the years from 0 to $N-1$ in chronological order, so year $N-1$ is the most recent one. The weather in year $i$ decides how fast the herd grows, and the growth rate is a positive integer $X[i]$ . If Mansur has $h$ horses at the start of year $i$ , he has $h \times X[i]$ horses at the end of that year.

Horses are sold only at the end of a year. At the end of year $i$ one horse sells for a positive integer $Y[i]$ , and there is no limit on how many of the horses he holds at that moment he sells.

Mansur wants to know how much money he could have made over the last $N$ years if he had picked the selling times perfectly. Through the evening his memory sharpens, so he corrects the numbers $M$ times. Each correction replaces one $X[i]$ or one $Y[i]$ with a new value, and the corrections pile up. The same position is corrected more than once in some cases.

Compute the largest amount of money he could make with the initial numbers, and the largest amount after each correction. The answer gets very large, so print it modulo $10^9+7$ .

Input

The first line contains the number of years $N$ .

The second line contains $N$ integers $X[0]$ to $X[N-1]$ , separated by spaces.

The third line contains $N$ integers $Y[0]$ to $Y[N-1]$ , separated by spaces.

The fourth line contains the number of corrections $M$ .

Each of the next $M$ lines contains one correction in the form type pos val. If type is 1, then $X[pos]$ becomes val. If type is 2, then $Y[pos]$ becomes val.

Limits:

$1 \le N \le 500\,000$
$0 \le M \le 100\,000$
$1 \le X[i] \le 10^9$ and $1 \le Y[i] \le 10^9$ , both for the initial values and after every correction
type is 1 or 2, $0 \le pos \le N-1$ , and $1 \le val \le 10^9$

Output

Print $M+1$ lines.

The first line holds the largest amount of money Mansur could make with the initial numbers. The $i$ -th line after that holds the largest amount once the first $i$ corrections have all been applied.

Every value is printed modulo $10^9+7$ .

Examples3

Example 1
Input
```
3
2 1 3
3 4 1
1
2 1 2
```
Expected output
```
8
6
```
Example 2
Input
```
1
5
7
0
```
Expected output
```
35
```

Example 3

Input

Expected output

9
10
36