Horses#7769
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. 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 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 , Mansur remembers a positive integer growth coefficient x_i. If you started year with horses, you ended the year with h \cdot x_i horses in your herd.
Horses could only be sold at the end of a year. For each year , Mansur remembers a positive integer y_i: the price for which he could sell a horse at the end of year . 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 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 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.
The first line contains the number of years (1 \le n \le 500000). Second line gives the growth coefficients x_0, x_1, ... x_{n-1} at the end of the -th year (0 \le i \le n - 1), and third line gives the prices y_0, y_1, ... y_{n-1} of one horse at the end of -th year (0 \le i \le n - 1). The next line gives the number of updates (1 \le m \le 10^5). Each of the next lines gives three integers (type = 1 for UpdateX, type = 2 for UpdateY, 0 \le pos \le n - 1). All the initial, as well as updated values of X and Y arrays are between and 10^9 inclusive.
Print in the first line the maximal amount of money (modulo 10^9 + 7) that Mansur could get for theseinitial values of X and Y. Then for each update print the maximal amount of money (modulo 10^9 + 7) that Mansur could get after this update.
Suppose that there are n = 3 years, with the following information:
For these initial values, Mansur can earn the most if he sells both his horses at the end of year . The entire process will look as follows:
Initially, Mansur has horse.
After year he will have 1 \cdot x_0 = 2 horses.
After year he will have 2 \cdot x_1 = 2 horses. He can now sell those two horses. The total profit will be 2 \cdot y_1 = 8.
Then, suppose that there is m = 1 update: changing y_1 to . After the update we will have:
In this case, one of the optimal solutions is to sell one horse after year and then three horses after year . The entire process will look as follows:
Initially, Mansur has horse.
After year he will have 1 \cdot x_0 = 2 horses. He can now sell one of those horses for 1 \cdot y_0 = 3, and have one horse left.
After year he will have 1 \cdot x_1 = 1 horse.
After year he will have 1 \cdot x_2 = 3 horses. He can now sell those three horses for 3 \cdot y_2 = 3. The total amount of money is 3 + 3 = 6.
Example 1