Overview

We consider how much Takahashi has closed the gap to Aoki as the per-second difference \(C_i = B_i - A_i\).
Using the total per cycle and the prefix sums within a cycle, we process each query in \(O(N)\).

Analysis

The distance gap at time \(0\) is \(d\).
In a given 1-second interval, Aoki advances \(A_i\) and Takahashi advances \(B_i\), so the distance gap shrinks by

\(B_i - A_i\)

in that 1 second.

Therefore, we define

\(C_i = B_i - A_i\)

Let \(X(t)\) be the total amount Takahashi has closed in on Aoki by time \(t\). The condition for Takahashi to catch up is

\(X(t) \geq d\)

---

We define the prefix sums within one cycle of period \(N\) as

\(P_i = C_1 + C_2 + \cdots + C_i\)

Also, the total increase over one full cycle is

\(S = C_1 + C_2 + \cdots + C_N\)

Expressing time \(t\) as

\(t = qN + r \quad (0 \leq r < N)\)

means that after \(q\) full cycles, we have advanced \(r\) seconds into the current cycle.
The cumulative value at this point is

\(X(t) = qS + P_r\)

---

Naive Simulation Is Too Slow

For each 2 d query, if we simulate second by second, the answer could be around \(10^{15}\).
Therefore, we cannot simply advance time step by step.

Also, since \(C_i\) can be negative, the cumulative sum \(X(t)\) is not necessarily monotonically increasing.
Therefore, simple binary search is also not applicable.

---

Case Analysis Based on the Cycle Total \(S\)

Case \(S \leq 0\)

Since the total per cycle does not increase, going to later cycles does not increase the cumulative value at the same position within a cycle.

In other words, if Takahashi can catch up at all, he must do so within the first \(N\) seconds.

Therefore, we check \(P_1, P_2, \dots, P_N\) in order and find the first position where it becomes at least \(d\).
If no such position exists, the answer is \(-1\).

---

Case \(S > 0\)

Since the cumulative value increases with each cycle, Takahashi will eventually catch up.

However, since he might catch up in the middle of a cycle, the maximum prefix sum within a cycle is important.

The maximum value within one cycle is

\(M = \max(P_0, P_1, \dots, P_N)\)

The maximum value reachable within the next cycle after \(q\) complete cycles is

\(qS + M\)

Therefore, the earliest cycle number \(q\) where Takahashi can catch up is the smallest \(q\) satisfying

\(qS + M \geq d\)

If \(d \leq M\), then he can catch up within the first cycle.

Otherwise,

\(q = \left\lceil \frac{d - M}{S} \right\rceil\)

By skipping ahead \(q\) cycles, the remaining required value becomes

\(d - qS\)

Then we find the first \(i\) within the cycle such that

\(P_i \geq d - qS\)

and the answer is

\(qN + i\)

Algorithm

First, for each \(i\), we store

\(C_i = B_i - A_i\)

We also maintain the total over one full cycle

\(S = \sum C_i\)

Each query is processed as follows.

---

1 i a b

Update the \(i\)-th value.

The new difference is

\(b - a\)

We also update the cycle total \(S\) by the difference from the old \(C_i\).

---

2 d

Case \(S \leq 0\)

Scan through the cycle from the beginning, computing the prefix sum.

Output the first time the prefix sum becomes at least \(d\).
If it never reaches \(d\) by the end, output \(-1\).

---

Case \(S > 0\)

First, find the maximum prefix sum \(M\) within one cycle.

• If \(d \leq M\), the answer is within the first cycle
• If \(d > M\), skip ahead to just before the cycle where catching up becomes possible

The number of cycles to skip is

\(q = \left\lceil \frac{d - M}{S} \right\rceil\)

The ceiling division for integers can be computed as

\(\left\lceil \frac{x}{S} \right\rceil = \frac{x + S - 1}{S}\)

Then, scan through the cycle from the beginning and find the first \(i\) such that

\(P_i \geq d - qS\)

The answer is

\(qN + i\)

Complexity

• Time complexity: \(O(NQ)\)
• Space complexity: \(O(N)\)

Since the constraints guarantee \(NQ \leq 10^7\), scanning through the cycle in \(O(N)\) per query is fast enough.

Implementation Notes

• The values to store directly are not the speeds \(A_i, B_i\), but the differences \(C_i = B_i - A_i\).

• For update queries, update both \(C_i\) and the cycle total \(S\) simultaneously.

• Since \(d\) can be up to \(10^{15}\), and speed differences and cumulative values can also be large, 64-bit integers are required. In Python, integers have arbitrary precision, so this is not an issue.

• Since \(C_i\) can be negative, you must not assume “the prefix sum is monotonically increasing.” Always check within the cycle from the beginning in order.

  Source Code

import sys

def main():
    data = sys.stdin.buffer.read().split()
    p = 0

    N = int(data[p])
    Q = int(data[p + 1])
    p += 2

    C = [0] * N
    total = 0

    for i in range(N):
        a = int(data[p])
        b = int(data[p + 1])
        p += 2
        v = b - a
        C[i] = v
        total += v

    out = []
    append = out.append
    n = N

    for _ in range(Q):
        typ = data[p]
        p += 1

        if typ == b'1':
            idx = int(data[p]) - 1
            a = int(data[p + 1])
            b = int(data[p + 2])
            p += 3

            nv = b - a
            total += nv - C[idx]
            C[idx] = nv

        else:
            d = int(data[p])
            p += 1

            if total <= 0:
                cur = 0
                ans = -1
                i = 0
                for v in C:
                    i += 1
                    cur += v
                    if cur >= d:
                        ans = i
                        break
                append(str(ans))

            else:
                cur = 0
                mx = 0
                for v in C:
                    cur += v
                    if cur > mx:
                        mx = cur

                diff = d - mx
                if diff > 0:
                    q = (diff + total - 1) // total
                    target = d - q * total
                    base = q * n
                else:
                    target = d
                    base = 0

                cur = 0
                i = 0
                for v in C:
                    i += 1
                    cur += v
                    if cur >= target:
                        append(str(base + i))
                        break

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.