Battlefield Survival Optimization

You are given n military units. The i-th unit initially has a_i soldiers and a consumption value m_i. Every integer minute (starting at minute 1) each unit undergoes an update: its current number of soldiers becomes \(\lfloor\frac{x}{m_i}\rfloor\) where x is the number of soldiers allocated to that unit at that minute. If at any minute, after the update, at least one unit’s soldier count becomes 0, Happybob loses the war. We define the survival time as the last minute index for which every unit still had at least 1 soldier (i.e. the minute immediately before a unit drops to 0).

However, Happybob is clever. Between any two integer minutes (i.e. at non‐integer times) he is allowed to transfer soldiers between units. Formally, he may choose two distinct units i and j and an integer x satisfying 1 ≤ x ≤ a_i, and then update the numbers to a_i − x and a_j + x respectively. There is no limit to how many such transfers may be performed between the integer minute updates.

With optimal transfers, Happybob wants to maximize the survival time of his army. As his trusted strategist, you are to answer q operations. Initially, at minute 0, the units have counts a_i and consumption values m_i (i = 1,2, …, n). Note: Throughout the problem, all indices i and j are subject to 1 ≤ i, j ≤ n and i ≠ j.

The operations are of three types:

• Type 1: 1 i x — set the soldier count a_i to x (1 ≤ x ≤ 10⁹).
• Type 2: 2 i x — set the consumption value m_i to x (1 ≤ x ≤ 10⁶).
• Type 3: 3 — output the maximum survival time achievable by optimal transfers. This operation does not change any a_i or m_i.

How to compute the maximum survival time?

At each integer minute update, before the decay happens, you may redistribute the total number of soldiers arbitrarily among units. In order for every unit to survive the upcoming update, each unit i must be allocated at least m_i soldiers (since \(\lfloor\frac{m_i}{m_i}\rfloor = 1\)). Let S denote the total number of soldiers and M = \(\sum_{i=1}^{n} m_i\) be the total minimum required soldiers. Moreover, to maximize the post‐update total, you would allocate extra soldiers in multiples of m_i — and it turns out that the optimal strategy is to put all extra soldiers into the unit with the minimum consumption value r = \(\min_{i}(m_i)\) (since additional multiples of r yield extra survivors).

Thus if you have a total of S soldiers at the beginning of a minute, and S ≥ M, the best you can guarantee after the update is:

[ S_{next} = n + \left\lfloor\frac{S - M}{r}\right\rfloor. ]

You then repeat the process with the new total S_next. The survival time is defined as the maximum number T such that you can perform T updates (i.e. T minutes) before the total soldiers fall below M (at which point you cannot allocate enough soldiers to every unit).

Infinite Survival: If all consumption values are 1 (so that M = n and r = 1), the soldier count will never decrease (since \(S_{next} = n + (S - n) = S\)). In this case, output -1 to indicate infinite survival time.

---

Input Format

---

Output Format

inputFormat

The input begins with a line containing two integers n and q separated by a space.

The second line contains n integers representing the initial soldier counts for each unit.

The third line contains n integers representing the consumption values for each unit.

Then follow q lines, each describing an operation in one of the three forms:

• 1 i x — update a_i to x.
• 2 i x — update m_i to x.
• 3 — query the maximum survival time.

outputFormat

For each operation of type 3, output the maximum survival time (in minutes) on a separate line. If the survival time is infinite, output -1.

sample

2 3
13 10
4 6
3
1 1 5
3

1
1

</p>