Happybob's Game (UBC001D)

**注：本题中所有 $i,j$ 均默认 $1\le i,j\le n$ 且 $i\not = j$。** Happybob 的游戏角色正在进行战争。 他有 $n$ 个部队，每个部队有 $a_i$ 个人，并且有消耗值 $m_i$，表示每过 $1$ 分钟第 $i$ 个部队的人会变成 $⌊\frac{a_i}{m_i}⌋$，一旦其中一支部队人数变成 $0$，Happybob 就失败了。设一开始为第 $0$ 分钟，定义存活时间为 Happybob 的其中一支部队人数变成 $0$ 的上一分钟。**可参考样例解释。** 但是 Happybob 不甘就这样就被消灭，他想到了好办法：他可以在**任意不是整数分钟**的时间将一个部队的人调一部分到另一个部队。形式化来说，取两支军队 $a_i, a_j$ 以及一个调换人数 $x$ 满足 $1\le x\le a_i$，使 $a_i,a_j$ 分别变成 $a_i-x,a_j+x$。注意，在两个整数分钟间，他可以调换任意多次。 Happybob 发现，这样可以有效地提升部队存活时间。现在你作为 Happybob 最信任的参谋长，你可以帮他调兵遣将。 接下来给你 $q$ 次操作，每次操作是以下操作中的一个： - 操作 $1$，形如 `1 i x`，表示 Happybob 的第 $i$ 支部队的人数 $a_i$ 变成了 $x$ （$1\le x\le 10^9$）。 - 操作 $2$，形如 `2 i x`，表示 Happybob 的第 $i$ 支部队的消耗值 $m_i$ 变成了 $x$（$1\le x\le 10^6$）。 - 操作 $3$，形如 `3`，表示让你输出 Happybob 理论上通过上述调兵遣将法最久的存活时间。注意，此操作**不会**改变 $a_i$ 或 $m_i$ 的值。

第一行，两个正整数 $n,q$。 接下来两行，每行 $n$ 个正整数，分别表示 $a$ 数组与 $m$ 数组。 接下来 $q$ 行，每行都是上述三种操作之一。

假设共有 $opt$ 次操作 $3$，那么你的答案应该有 $opt$ 行，每行表示当前状态下 Happybob 的最长可能存活时间。如果 Happybob 的军队可以无限地活下去，输出 `-1`。

2 10
29 5
7 2
1 2 3
2 1 3
3
1 1 1
1 2 1
2 1 1
2 2 1
3
2 1 2
3

3
-1
0

### 样例说明 对于第一个操作 $3$，Happybob 可以这样调动军队： | 时刻（分） | 第一支军队人数 | 第二支军队人数 | | :----------: | :----------: | :----------: | | $0$ | $29$ | $3$ | | $0.5$ | $10$ | $22$ | | $1$ | $3$ | $11$ | | $1.5$ | $6$ | $8$ | | $2$ | $2$ | $4$ | | $2.5$ | $3$ | $3$ | | $3$ | $1$ | $1$ | | $3.5$ | $1$ | $1$ | | $4$ | $0$ | $0$ | ### 数据范围 对于 $100\%$ 的数据，$1\le n \le 5\times 10^6$，$1\le q \le 10^5$。保证对于所有 $a_i,m_i$，$1\le a_i\le 10^9$，$1\le m_i\le 10^6$。