题目描述

注：本题中所有 $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 可以这样调动军队：

数据范围

对于 $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$。