题目背景

自从山哥利用远古石工智能发现了呆河马之后，从此就一发不可收拾。呆河马这种生物是非常的值钱的，光是它的皮就可以用来治愈这种病，因此，一批又一批呆河马养殖园开始养殖呆河马的计划。

题目描述

作为养殖场的大佬，阳阳引进了养殖呆河马的技术，而且她有一个团队来研究呆河马的养殖技巧来制定养殖规划，并在今年购入了 1 只呆河马。她们制定了从今年(即第 0 年)到第 $n-1$年的养殖呆河马的计划。其中她们确定了一个繁殖系数 $x_i$，其中 $x_i$ 代表着在第 $i$ 年，若第 $i$ 年年初时有 $h$ 只呆河马，则第 $i$ 年年末(第 $i+1$ 年年初)会有 $h\cdot x_i$ 只呆河马，且这个时候养殖园可以杀掉一些呆河马赚钱，每只呆河马的可以赚到的利润为 $p_i$。

而每次阳阳会预估到总会有一些意外发生，因此她会对养殖的预测进行 $m$ 次修改，且每次修改只会涉及一个 $x_i$ 或 $p_i$ 的修改。注意：修改是累加的，即每次涉及修改时都应该考虑之前的所有的修改。作为养殖场的场长阳阳，她肯定希望养殖呆河马可以得到收益最大，但是阳阳的养殖场的呆河马实在是太多了，她忙不过来了，因此需要你的帮忙。

你的任务是，输出她初始与每次修改后，养殖呆河马可以获取最大的利润。

输入格式

第一行为一个正整数 $n$，描述阳阳的规划的年数。

接下来一行，有 $n$ 个正整数，第 $i$ 个数字为题中所描述的 $x_{i-1}$。

接下来一行，有 $n$ 个正整数，第 $i$ 个数字为题中所描述的 $p_{i-1}$。

接下来一行，为 1 个正整数 $m$，描述阳阳修改计划的次数。

接下来 $m$ 行，每行 3 个正整数 $type$， $pos$， $val$，若 $type=1$ 则说明把 $x_{pos}$ 的值修改为 $val$，若$type=2$，则说明把 $p_{pos}$ 的值修改为 $val$。

输出格式

输出 $m+1$ 行， 每行一个正整数。第 1 行输出在最初条件时， 养殖呆河马可获得最大的利润，接下来 $m$ 行，分别输出每次修改后，养殖呆河马可获得最大的利润。

由于答案有可能会极大，因此你只需每次输出答案对 $10^9+7$ 取模后的结果。

3
2 1 3
3 4 1
1
2 1 2

8
6

提示

子任务

提示

输入数据规模较大，请注意读入效率。

题解

https://www.luogu.org/discuss/show?postid=52662