题目描述

像他的祖先一样，Mansur 喜欢繁殖马匹。目前，他拥有哈萨克斯坦最大的马场。以前情况可不是这样，$N$ 年前 Mansur 年轻时，他只拥有一匹马，但他一直梦想着成为富豪，最终,他美梦成真。

按照时间的先后顺序将年份编号为 $0$ 到 $N-1$（即 $N-1$ 年是最近的一年）。每年的天气会影响马匹的繁殖。Mansur 用一个正整数 $X[i]$ 记录第 $i$ 年的繁殖系数，如果第 $i$ 年开始时有 $h$ 匹马，那么这一年结束时会有 $h \times 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$，表示总共有 $N$ 年。
• 第 $2$ 行，共 $N$ 个正整数 $X[0],\cdots,X[N - 1]$，对于 $0\le i \le N-1$，$X[i]$ 表示 $i$ 年的繁殖系数。
• 第 $3$ 行，共 $N$ 个正整数 $Y[0],\cdots,Y[N - 1]$，对于 $0\le i \le N-1$，$Y[i]$ 表示 $i$ 年末出售一匹马的价格。
• 第 $4$ 行，一个整数 $M$，表示更新次数。
• 第 $5,\cdots,M+4$ 行，每行 $3$ 个数字 $type$，$pos$，$val$ （$type=1$ 表示更改 $X[ pos ]$ 为 $val$，$type=2$ 表示更改 $Y[ pos ]$ 为 $val$）。

输出格式

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

3
2 1 3
3 4 1
1
2 1 2

8
6

提示

对于 $100\%$ 的数据，$1\le N\le 5\times 10^5$，$0 \le M \le 10^5$。