<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

148. B-Station
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard input
output: standard output



There is a half-waterlogged underwater station not far from the famous country Berland. The station consists of N levels. The following information is known about each level: Wi - the weigth of water on i-th before the act of terrorism, Li - the weight of water the i-th level can hold, and Pi - amount of money terrorist are required to depressurize i-th level. All the water from the depressurized level pours to the next level. If the weight of the water on i-th level is more then Li, then it becomes depressurized. The terrorists from Pivland want to depressurize the last (N-th) level spending the least amount of money. They hired you to do this.

Input
The first line of input contains the natural number N (1<=N<=15000). Each of the following N lines contains 3 numbers Wi, Li, Pi (0<=Wi,Li,Pi<=15000).

Output
Write to the output the numbers of levels, which must be depressurized.

Sample test(s)

Input
3
1000 1000 1
0 1000 2
2 10 100

Output
1
2
Author:	Andrew V. Lazarev
Resource:	Saratov Regional Olympiad, 2002
Date:	Spring, 2002

<|response|>
1. Abridged Problem Statement  
You have N stacked levels (1 ≤ N ≤ 15000). Level i initially holds Wᵢ weight of water and can support up to Lᵢ before it leaks. You may also choose to manually depressurize (leak) level i at cost Pᵢ. Whenever a level leaks—either automatically because accumulated water > Lᵢ or because you paid Pᵢ—all its water flows to the next level. You want to ensure that the N-th level leaks, minimizing total paid cost. Output the list of levels you choose to depressurize (in increasing order), one per line.

2. Key Observations  
- Once a level leaks, all its water moves downward; water only accumulates from the chosen “start” level downward.  
- If at level i the current accumulated water w satisfies w > Lᵢ, it leaks automatically (no cost). Otherwise you must pay Pᵢ to force it to leak (so water continues downward).  
- If w ever exceeds the maximum possible Lᵢ (≤ 15000), then for all further levels w > Lᵢ holds automatically; we can stop checking costs.  
- The process is fully determined by the first level s you trigger (you reset w=0 there). Try all s∈[1..N], simulate downward, sum the required Pᵢ, and pick the minimal-cost start. Then rerun from that start to record exactly which levels were paid for.

3. Full Solution Approach  
a. Read N and arrays W[1..N], L[1..N], P[1..N].  
b. Initialize bestCost = ∞, bestStart = 1.  
c. For start in 1..N:  
   • Set w = 0, cost = 0.  
   • For i from start to N:  
     – w += W[i]  
     – If w ≤ L[i], we must pay cost += P[i]; otherwise it leaks automatically.  
     – If w > MAX_L (15000), break (all further leak automatically).  
   • If cost < bestCost, update bestCost and bestStart = start.  
d. Now rerun the same simulation from bestStart, collecting each i where w≤L[i] (i.e., where you paid P[i]), and output those indices in increasing order.

Time complexity is O(N²) in the worst case, but the early break when w > 15000 usually keeps the inner loop short enough for N up to 15000.

4. C++ Solution
```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<tuple<int, int, int>> a;

void read() {
    cin >> n;
    a.resize(n);
    for(auto& [x, y, z]: a) {
        cin >> x >> y >> z;
    }
}

void solve() {
    // We pick a single top level to start the chain reaction by paying to
    // depressurize it: its water W pours onto the next level, and from there
    // on the falling water w_fall accumulates downward. At each level, if the
    // accumulated water already exceeds the level's capacity L it breaks for
    // free and we keep falling; otherwise we must pay P to break it (and add
    // its own W to the cascade). The total cost of a given start is the sum of
    // the P of the levels we had to pay for; once w_fall exceeds the maximum
    // possible capacity (15000) the rest collapses for free, so we stop early.
    // We try every start, keep the cheapest, and replay it to list which
    // levels we ended up paying to depressurize.

    int ans = get<2>(a[n - 1]);
    int best_pos = n - 1;

    for(int start = 0; start < n; start++) {
        int w_fall = 0, candidate = 0;
        for(int i = start; i < n; i++) {
            auto [x, y, z] = a[i];
            w_fall += x;
            if(w_fall <= y) {
                candidate += z;
            } else if(w_fall > 15000) {
                break;
            }
        }

        if(candidate < ans) {
            ans = candidate;
            best_pos = start;
        }
    }

    int w_fall = 0;
    vector<int> best;
    for(int i = best_pos; i < n; i++) {
        auto [x, y, z] = a[i];
        w_fall += x;
        if(w_fall <= y) {
            best.push_back(i + 1);
        }
    }

    for(auto x: best) {
        cout << x << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    W, L, P = [], [], []
    ptr = 1
    for _ in range(n):
        w_i = int(data[ptr]); l_i = int(data[ptr+1]); p_i = int(data[ptr+2])
        ptr += 3
        W.append(w_i)
        L.append(l_i)
        P.append(p_i)

    MAX_L = 15000
    best_cost = float('inf')
    best_start = 0

    # Try every starting level
    for s in range(n):
        w = 0
        cost = 0
        # Cascade from s to n-1
        for i in range(s, n):
            w += W[i]
            if w <= L[i]:
                # must pay to depressurize
                cost += P[i]
            # else auto‐leaks
            if w > MAX_L:
                # no more payments needed
                break

        if cost < best_cost:
            best_cost = cost
            best_start = s

    # Re-run from best_start to collect paid levels
    w = 0
    result = []
    for i in range(best_start, n):
        w += W[i]
        if w <= L[i]:
            result.append(str(i + 1))  # convert to 1-based
        if w > MAX_L:
            break

    # Print each chosen level on its own line
    sys.stdout.write("\n".join(result))

if __name__ == "__main__":
    main()
```