Overview

The daily fund changes \(A_i-B_i-C_i\) repeat infinitely with period \(N\).
For each query, we efficiently find the first day when the cumulative funds become negative, starting from a specified day.

Analysis

First, let the daily fund change be

\[ D_i = A_i - B_i - C_i \]

If we simulate day by day for each query, it could take an extremely long number of days until bankruptcy.
Moreover, even just checking up to \(N\) days for each of the \(Q\) queries results in \(O(NQ)\) in the worst case, which is too slow for \(N+Q \leq 2 \times 10^5\).

The key insight is that the business plan repeats with period \(N\).

Let the starting day be \(L\), and in 0-indexed terms, \(s=L-1\).
The cumulative fund increase from the start up to \(k\) days later is, on the cyclic sequence:

\[ D_s + D_{s+1} + \cdots + D_{s+k-1} \]

To compute this efficiently, we create a prefix sum array of \(D\) concatenated twice.

If we let the prefix sum be \(P\), then the increase from starting day \(s\) over \(k\) days is

\[ P_{s+k} - P_s \]

---

First, consider only the first \(N\) days from the start, i.e., one full cycle.

The minimum increase in funds within that one cycle is

\[ \min_{1 \leq k \leq N} (P_{s+k} - P_s) \]

Let this value be \(\mathrm{mn}\).

If the initial capital is \(S\), then the minimum funds during the first cycle is

\[ S + \mathrm{mn} \]

• If \(S+\mathrm{mn}<0\), bankruptcy occurs within the first cycle.
• Otherwise, bankruptcy does not occur in the first cycle.

Next, let the total fund change over one full cycle be

\[ T = D_1 + D_2 + \cdots + D_N \]

If bankruptcy does not occur in the first cycle:

• If \(T \geq 0\), the capital at the start of each cycle never decreases, so bankruptcy never occurs.
• If \(T < 0\), the capital decreases by \(-T\) yen each cycle, so bankruptcy will eventually occur.

---

To find the specific day of bankruptcy, we need to find “the first position in a range of the prefix sum array where the value falls below a certain threshold.”

Since the prefix sum sequence is not necessarily monotonic, binary search cannot be used.
Instead, we build a segment tree that maintains range minimum values over the prefix sum array, enabling us to:

• Query range minimum values
• Find the first position within a range where the value falls below a specified threshold

efficiently.

Algorithm

1. Preprocessing

Store the daily changes in an array as

\[ D_i = A_i - B_i - C_i \]

Next, create a prefix sum \(P\) for the sequence of length \(2N\) obtained by repeating \(D\) twice.

\[ P_0 = 0 \]

\[ P_{i+1} = P_i + D_{i \bmod N} \]

This allows us to treat the cumulative increase from any starting position \(s\) for up to \(N\) days as a contiguous interval.

Also, let the total increase over one full cycle be

\[ T = P_N \]

Build a segment tree that manages range minimum values over the prefix sum \(P\).

---

2. Processing Each Query

Suppose a query gives starting day \(L\) and initial capital \(S\).
The 0-indexed starting position is

\[ s = L - 1 \]

The prefix sum range corresponding to one cycle is

\[ P_{s+1}, P_{s+2}, \ldots, P_{s+N} \]

In code, we look at the half-open interval

\[ [s+1, s+N+1) \]

We query the segment tree for the minimum value in this range.

\[ \mathrm{mn} = \min(P_{s+1}, \ldots, P_{s+N}) - P_s \]

This is “the minimum cumulative fund change within one cycle from the start.”

---

3. When Bankruptcy Occurs in the First Cycle

If

\[ S + \mathrm{mn} < 0 \]

then bankruptcy occurs somewhere in the first cycle.

The bankruptcy condition is that for some \(k\):

\[ S + (P_{s+k} - P_s) < 0 \]

Rearranging:

\[ P_{s+k} < P_s - S \]

Therefore, we search for the first position \(i\) in the interval \([s+1, s+N+1)\) where

\[ P_i < P_s - S \]

The answer is

\[ i - s \]

days.

---

4. When Bankruptcy Does Not Occur in the First Cycle

If bankruptcy does not occur in the first cycle, we then check \(T\).

Case \(T \geq 0\)

Since funds do not decrease with each cycle, bankruptcy never occurs.

The answer is 0.

Case \(T < 0\)

Funds decrease by \(d=-T\) with each cycle.

After completing \(c\) cycles, the capital is

\[ S - cd \]

The minimum funds within that cycle is

\[ S - cd + \mathrm{mn} \]

We find the smallest \(c\) for which this first becomes negative.

\[ S - cd + \mathrm{mn} < 0 \]

\[ cd > S + \mathrm{mn} \]

Therefore,

\[ c = \left\lfloor \frac{S+\mathrm{mn}}{d} \right\rfloor + 1 \]

This means we skip \(c\) complete cycles, and bankruptcy occurs within the next cycle.

The capital at that point is

\[ S + cT \]

Let this capital be \(\mathrm{capital}\). The bankruptcy condition is

\[ \mathrm{capital} + (P_i - P_s) < 0 \]

i.e.,

\[ P_i < P_s - \mathrm{capital} \]

Again using the segment tree, we find the first position \(i\) in the interval \([s+1, s+N+1)\) that satisfies this condition.

The answer is

\[ cN + (i-s) \]

Complexity

• Time complexity: \(O((N+Q)\log N)\)
• Space complexity: \(O(N)\)

Building the segment tree takes \(O(N)\), and each query performs a range minimum query and a “find first position below threshold” search in \(O(\log N)\).

Implementation Notes

The bankruptcy condition is “funds become less than \(0\) yen,” so the check uses < not <=.

For example, if funds become exactly \(0\) yen, it is not bankruptcy.

Therefore, the condition for finding the position is also a strict inequality:

\[ P_i < P_s - S \]

Also, prefix sums and the answer in days can become very large.
In Python, integers have arbitrary precision so this is not an issue, but in C++ or similar languages, you need to use long long.

Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)

    N = next(it)
    Q = next(it)

    diff = [0] * N
    for i in range(N):
        a = next(it)
        b = next(it)
        c = next(it)
        diff[i] = a - b - c

    M = 2 * N + 1
    pref = [0] * M
    for i in range(2 * N):
        pref[i + 1] = pref[i] + diff[i % N]

    total = pref[N]

    INF = 10**30
    size = 1
    while size < M:
        size <<= 1

    seg = [INF] * (2 * size)
    seg[size:size + M] = pref

    for i in range(size - 1, 0, -1):
        v1 = seg[i << 1]
        v2 = seg[i << 1 | 1]
        seg[i] = v1 if v1 < v2 else v2

    def range_min(l, r):
        l += size
        r += size
        res = INF
        sg = seg
        while l < r:
            if l & 1:
                if sg[l] < res:
                    res = sg[l]
                l += 1
            if r & 1:
                r -= 1
                if sg[r] < res:
                    res = sg[r]
            l >>= 1
            r >>= 1
        return res

    def first_less(l, r, x):
        l += size
        r += size
        left = []
        right = []
        sg = seg

        while l < r:
            if l & 1:
                left.append(l)
                l += 1
            if r & 1:
                r -= 1
                right.append(r)
            l >>= 1
            r >>= 1

        for node in left:
            if sg[node] < x:
                while node < size:
                    lc = node << 1
                    if sg[lc] < x:
                        node = lc
                    else:
                        node = lc | 1
                return node - size

        for node in reversed(right):
            if sg[node] < x:
                while node < size:
                    lc = node << 1
                    if sg[lc] < x:
                        node = lc
                    else:
                        node = lc | 1
                return node - size

        return -1

    ans = []
    for _ in range(Q):
        L = next(it)
        S = next(it)

        s = L - 1
        base = pref[s]
        l = s + 1
        r = s + N + 1

        mn = range_min(l, r) - base

        if S + mn < 0:
            threshold = base - S
            idx = first_less(l, r, threshold)
            ans.append(str(idx - s))
        else:
            if total >= 0:
                ans.append("0")
            else:
                d = -total
                cycles = (S + mn) // d + 1
                capital = S + cycles * total
                threshold = base - capital
                idx = first_less(l, r, threshold)
                ans.append(str(cycles * N + (idx - s)))

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

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.