### IOI '15 - Almaty, Kazakhstan

## Horses

Mansur loves to breed horses, just like his ancient ancestors did. He now has the largest herd in Kazakhstan. But this was not always the case. `N` years ago, Mansur was just a dzhigit (Kazakh for *a young man*) and he only had a single horse. He dreamed to make a lot of money and to finally become a bai (Kazakh for *a very rich person*).

Let us number the years from 0 to `N` − 1 in chronological order (i.e., year `N` − 1 is the most recent one). The weather of each year influenced the growth of the herd. For each year `i`, Mansur remembers a positive integer growth coefficient `X`[`i`]. If you started year `i` with `h` horses, you ended the year with `h` • `X`[`i`] horses in your herd.

Horses could only be sold at the end of a year. For each year `i`, Mansur remembers a positive integer `Y`[`i`]: the price for which he could sell a horse at the end of year `i`. After each year, it was possible to sell arbitrarily many horses, each at the same price `Y`[`i`].

Mansur wonders what is the largest amount of money he could have now if he had chosen the best moments to sell his horses during the `N` years. You have the honor of being a guest on Mansur's toi (Kazakh for *holiday*), and he asked you to answer this question.

Mansur's memory improves throughout the evening, and so he makes a sequence of `M` updates. Each update will change either one of the values `X`[`i`] or one of the values `Y`[`i`]. After each update he again asks you the largest amount of money he could have earned by selling his horses. Mansur's updates are cumulative: each of your answers should take into account all of the previous updates.
Note that a single `X`[`i`] or `Y`[`i`] may be updated multiple times.

The actual answers to Mansur's questions can be huge. In order to avoid working with large numbers, you are only required to report the answers modulo 10^{9} + 7.

### Example

Suppose that there are `N` = 3 years, with the following information:

0 | 1 | 2 | |
---|---|---|---|

X | 2 | 1 | 3 |

Y | 3 | 4 | 1 |

For these initial values, Mansur can earn the most if he sells both his horses at the end of year 1. The entire process will look as follows:

- Initially, Mansur has 1 horse.
- After year 0 he will have 1 •
`X`[0] = 2 horses. - After year 1 he will have 2 •
`X`[1] = 2 horses. - He can now sell those two horses. The total profit will be 2 •
`Y`[1] = 8.

Then, suppose that there is `M` = 1 update: changing `Y`[1] to 2. After this update we will have:

0 | 1 | 2 | |
---|---|---|---|

X | 2 | 1 | 3 |

Y | 3 | 2 | 1 |

In this case, one of the optimal solutions is to sell one horse after year 0 and then three horses after year 2. The entire process will look as follows:

- Initially, Mansur has 1 horse.
- After year 0 he will have 1 •
`X`[0] = 2 horses. - He can now sell one of those horses for
`Y`[0] = 3, and have one horse left. - After year 1 he will have 1 •
`X`[1] = 1 horse. - After year 2 he will have 1 •
`X`[2] = 3 horses. - He can now sell those three horses for 3 •
`Y`[2] = 3. The total amount of money is 3 + 3 = 6.

Your task is, given `N`, `X`, `Y` and the list of updates, before the first update and after every update, compute the maximal amount of money that Mansur could get for his horses, modulo 10^{9} + 7.

### Input Format

Line 1 of input will contain the single integer `N` representing the number of years.

Line 2 of input will contain the array `X`[0], …, `X`[`N` − 1], with adjacent numbers separated by a single space. For 0 ≤ `i` ≤ `N` − 1, `X`[`i`] gives the growth coefficient for year `i`. Note that this is the initial value given by Mansur (before any updates).

Line 3 of input will contain the array `Y`[0], …, `Y`[`N` − 1], with adjacent numbers separated by a single space. For 0 ≤ `i` ≤ `N` − 1, `Y`[`i`] gives the price of a horse after year `i`. Note that this is the initial value given by Mansur (before any updates).

Line 4 of input will contain the single integer `M`, representing the number of updates to follow.

Lines 5, … `M` + 4 will each contain three space-separated numbers `type`, `pos`, and `val` (`type` = 1 for updating `X` and `type` = 2 for updating `Y`). `pos` is an integer from the range 0, …, `N` − 1 and `val` is the new value for `Y`[`pos`].

### Output Format

The first line of output should contain a single integer representing the maximal amount of money Mansur could get for the initial values of `X` and `Y` (before any of the `M` updates), modulo 10^{9} + 7.

For each of the next `M` updates, output on a separate line containing a single integer representing the maximal amount of money Mansur could get after this update, modulo 10^{9} + 7.

### Sample Input

3 2 1 3 3 4 1 1 2 1 2

### Sample Output

8 6

### Subtasks

subtask | points | N | M | additional constraints |
---|---|---|---|---|

1 | 17% | 1 ≤ N ≤ 10 | M = 0 | X[i], Y[i] ≤ 10X[0] • X[1] • … • X[N − 1] ≤ 1,000 |

2 | 17% | 1 ≤ N ≤ 1,000 | 0 ≤ M ≤ 1,000 | none |

3 | 20% | 1 ≤ N ≤ 500,000 | 0 ≤ M ≤ 100,000 | X[i] ≥ 2 and val ≥ 2 for the initial values and updates to X correspondingly |

4 | 23% | 1 ≤ N ≤ 500,000 | 0 ≤ M ≤ 10,000 | none |

5 | 23% | 1 ≤ N ≤ 500,000 | 0 ≤ M ≤ 100,000 | none |

All Submissions

Best Solutions

**Point Value:** 15 (partial)

**Time Limit:** 2.00s

**Memory Limit:** 2048M

**Added:** Sep 05, 2015

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

ReaLNeroon Apr 20, 2016 - 5:46:04 pm UTC Online or Offline Queriesjargonon Apr 21, 2016 - 4:23:02 pm UTC Re: Online or Offline QueriesIf this doesn't answer your question please clarify.

Butaneon Sep 06, 2015 - 10:07:09 pm UTC incorrect sample output8

6

Alexon Sep 06, 2015 - 11:28:12 pm UTC Re: incorrect sample output