P10924 Happybob's Game (UBC001D)

**Note: In this problem, all $i, j$ are assumed to satisfy $1 \le i, j \le n$ and $i \not = j$.** Happybob's game character is fighting a war. He has $n$ armies. The $i$-th army has $a_i$ soldiers and a consumption value $m_i$, meaning that every $1$ minute, the number of soldiers in the $i$-th army becomes $⌊\frac{a_i}{m_i}⌋$. Once the number of soldiers in any army becomes $0$, Happybob loses. Let the beginning be minute $0$. Define the survival time as the minute right before one of Happybob's armies becomes $0$. **You may refer to the sample explanation.** However, Happybob is not willing to be wiped out like this. He comes up with a good idea: at **any time that is not an integer minute**, he can transfer some soldiers from one army to another. Formally, choose two armies $a_i, a_j$ and a transfer amount $x$ satisfying $1 \le x \le a_i$, and change $a_i, a_j$ into $a_i - x, a_j + x$ respectively. Note that between two integer minutes, he can perform transfers any number of times. Happybob finds that this can effectively increase the armies' survival time. Now, as Happybob's most trusted chief of staff, you need to help him deploy troops. Next, you are given $q$ operations. Each operation is one of the following: - Operation $1$, in the form `1 i x`, means the number of soldiers $a_i$ of Happybob's $i$-th army becomes $x$ ($1 \le x \le 10^9$). - Operation $2$, in the form `2 i x`, means the consumption value $m_i$ of Happybob's $i$-th army becomes $x$ ($1 \le x \le 10^6$). - Operation $3$, in the form `3`, means you should output the maximum survival time that Happybob can theoretically achieve using the troop-transfer method above. Note that this operation **does not** change the values of $a_i$ or $m_i$.

The first line contains two positive integers $n, q$. The next two lines each contain $n$ positive integers, representing the array $a$ and the array $m$. The next $q$ lines each describe one of the three operations above.

Suppose there are $opt$ operations of type $3$. Then your output should contain $opt$ lines, each line giving the maximum possible survival time under the current state. If Happybob's armies can survive forever, output `-1`.

### Sample Explanation For the first operation $3$, Happybob can move troops like this: | Time (min) | Soldiers in the first army | Soldiers in the second army | | :----------: | :----------: | :----------: | | $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$ | ### Constraints For $100\%$ of the testdata, $1 \le n \le 5 \times 10^6$, $1 \le q \le 10^5$. It is guaranteed that for all $a_i, m_i$, $1 \le a_i \le 10^9$, $1 \le m_i \le 10^6$. Translated by ChatGPT 5