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

按照时间的先后顺序将年份编号为 $0$ 到 $N-1$（即 $N-1$ 年是最近的一年）。每年的天气会影响马匹的繁殖。Mansur 用一个正整数 $X[i]$ 记录第 $i$ 年的繁殖系数，如果第 $i$ 年开始时有 $h$ 匹马，那么这一年结束时有 $h\cdot 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$ 后的结果即可。

设 $N=3$，$X$ 和 $Y$ 如下所示：

上述情况下，Mansur 在 1 年末卖掉他的马可以获得最大收益。具体说明如下：

• 起初，Mansur 有 1 匹马。
• 0 年末，他有 $1\cdot X[0]=2$ 匹马。
• 1 年末，他有 $2\cdot X[1]=2$ 匹马。
• 1 年末，他卖掉 2 匹马，总收益是 $2\cdot Y[1]=8$。

然后，设 $M=1$：将 $Y[1]$ 更新为 $2$，更新后的信息如下：

这种情况下，一种获得最大收益的方案是 0 年末卖掉 $1$ 匹马，然后 2 年末卖掉 $3$ 匹马。整个过程说明如下：

• 起初，Mansur 有1匹马。
• 0 年末，他有 $1\cdot X[0]=2$ 匹马。
• 0 年末，他卖掉 1 匹马，获益 $Y[0]=3$，于是他只剩下 1 匹马。
• 1 年末，他有 $1\cdot X[1]=1$ 匹马。
• 2 年末，他有 $1\cdot X[2]=3$ 匹马。
• 2 年末，他卖掉 3 匹马，获益 $3\cdot Y[2]=3$，总收益是 $3+3=6$。

任务

给定 $N,X,Y$ 和一系列更新操作。第一次更新前和每次更新后，计算 Mansur 可以获得的最大收益（注意：给出实际最大收益模 ${10}^9+7$ 后的结果）。你需要实现函数 init, updateX 和 updateY。

• init(N, X, Y) — grader首先调用此函数恰好一次。
  • N: 表示总共有 $N$ 年。
  • X: 长度为 $N$ 的数组，对 $0\le i\le N-1$，$X[i]$ 表示 $i$ 年的繁殖系数。
  • Y: 长度为 $N$ 的数组，对 $0\le i\le N-1$，$Y[i]$ 表示 $i$ 年末出售一匹马的价格。
  • 注意：X、Y均为Mansur给定的初值（更新前的值）。
  • init 函数结束后，数组 X 和 Y 仍然有效，你可以随意修改这两个数组的内容。
  • 该函数返回初始状态下，Mansur 获得的最大收益模 ${10}^9+7$ 后的值。
• updateX(pos, val)
  • pos: 一个整数，范围是 $0,\dots ,N-1$。
  • val: $X[pos]$ 更新后的值。
  • 该函数返回这次更新后Mansur获得的最大收益模 ${10}^9+7$ 的值。
• updateY(pos, val)
  • pos: 一个整数，范围是 $0,\dots ,N-1$。
  • val: $Y[pos]$ 更新后的值。
  • 该函数返回这次更新后Mansur获得的最大收益模 ${10}^9+7$ 的值。

$X[i]$、$Y[i]$ 的初值以及更新后值范围均为 $[1,{10}^9]$。 调用 init 后，grader 会调用 updateX 和 updateY 若干次，调用 updateX 和 updateY 的总次数是 $M$。

子任务

实现细节

你只能提交一个源文件实现如上所述的 init, updateX和updateY 函数，并且遵循下面的命名和接口。你需要包含头文件 horses.h。

int init(int N, int X[], int Y[]);
int updateX(int pos, int val);
int updateY(int pos, int val);

评测方式

评测系统将读入如下格式的输入数据：

• 第 $1$ 行：$N$
• 第 $2$ 行：$X[0]\dots X[N-1]$
• 第 $3$ 行：$Y[0]\dots Y[N-1]$
• 第 $4$ 行：$M$
• 第 $5，\dots ,M+4$ 行：每行 $3$ 个数字 type pos val（type = 1 表示 updateX，type = 2 表示 updateY）

评测系统将打印 init 的返回值，以及所有调用 updateX 和 updateY 后的返回值。

交互式类型的题目怎么本地测试

时间限制：$2\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例及测评库下载