[IOI2015]horses马

时间限制：30s 空间限制：1500MB

题目描述

像他的祖先一样，Mansur喜欢繁殖马匹。目前，他拥有哈萨克斯坦最大的马场。以前情况可不是这样，N年前Mansur年轻时，他只拥有一匹马，但他一直梦想着成为富豪，最终,他美梦成真。
按照时间的先后顺序将年份编号为0到N-1（即N-1年是最近的一年）。每年的天气会影响马匹的繁殖。Mansur用一个正整数X[i]记录第i年的繁殖系数，如果第i年开始时有h匹马，那么这一年结束时会有h•X[i]匹马。
每年，只有年底的时候可以出售马匹。Mansur用一个正整数Y[i]记录第i年末卖出一匹马的售价。Mansur可以卖出任意多匹马，每匹售价均为Y[i]。
现在，Mansur想知道如果在N年中，他总能在最佳时间出售马匹，他能获得的最⼤收益是多少？你正好在Mansur家做客，所以他想请你帮他回答这个问题。
Mansur对记录下的X和Y做了M次更新，每次更新，Mansur要么改变一个X[i] ，要么改变一个Y[i]。每次更新后，他都会问你出售马匹能获得的最大收益。Mansur的更新是累加的，即你的每个回答时都应该考虑之前的所有更新。注意：某个X[i]或者Y[i]可能会被更新多次。
对于Mansur的问题，实际的答案可能是一个非常大的数字，你只要给出实际答案模10^9+7后的结果即可。

输入格式

第1行: N
第2行: X[0] … X[N - 1]
第3行: Y[0] … Y[N - 1]
第4行: M
第5,…,M+4行: 每行3个数字type pos val (type=1表示updateX，type=2 表
示updateY)。
N: 表示总共有N年。
X: 长度为N的数组，对0≤i≤N-1,X[i]表示i年的繁殖系数。
Y: 长度为N的数组，对0≤i≤N-1,Y[i]表示i年末出售一匹马的价格。
注意：X、Y均为Mansur给定的初值（更新前的值）。
pos: 一个整数，范围是0，…,N-1。
val: X[pos]或Y[pos]更新后的值。

输出格式

共M+1行
第1行：一个整数表示初始状态下，Mansur获得的最大收益模10^9+7后的值。
第2,…,M+1行：每行一个整数，表示这次更新后Mansur获得的最大收益模10^9+7后的值。

样例输入

样例输出

8
6

提示

没有写明提示

题目来源

鸣谢yts1999上传