#define _USE_MATH_DEFINES #include using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3fLL; const double EPS = 1e-8; const int MOD = 1000000007; // const int MOD = 998244353; const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1}; template inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; } template inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(20); } } iosetup; template struct RMQ { RMQ(int sz, const Monoid UNITY) : UNITY(UNITY) { init(sz); dat.assign((n << 1) - 1, UNITY); } RMQ(const vector &a, const Monoid UNITY) : UNITY(UNITY) { int a_sz = a.size(); init(a_sz); dat.resize((n << 1) - 1); REP(i, a_sz) dat[n - 1 + i] = a[i]; for (int i = n - 2; i >= 0; --i) dat[i] = max(dat[(i << 1) + 1], dat[(i << 1) + 2]); } void update(int node, Monoid val) { node += n - 1; dat[node] = val; while (node > 0) { node = (node - 1) >> 1; dat[node] = max(dat[(node << 1) + 1], dat[(node << 1) + 2]); } } Monoid query(int a, int b) { return query(a, b, 0, 0, n); } int find(int a, int b, Monoid val) { return find(a, b, val, 0, 0, n); } Monoid operator[](const int idx) const { return dat[idx + n - 1]; } private: int n = 1; const Monoid UNITY; vector dat; void init(int sz) { while (n < sz) n <<= 1; } Monoid query(int a, int b, int node, int left, int right) { if (right <= a || b <= left) return UNITY; if (a <= left && right <= b) return dat[node]; return max(query(a, b, (node << 1) + 1, left, (left + right) >> 1), query(a, b, (node << 1) + 2, (left + right) >> 1, right)); } int find(int a, int b, Monoid val, int node, int left, int right) { if (dat[node] < val || right <= a || b <= left) return -1; if (right - left == 1) return node - (n - 1); int res_l = find(a, b, val, (node << 1) + 1, left, (left + right) >> 1); if (res_l != -1) return res_l; return find(a, b, val, (node << 1) + 2, (left + right) >> 1, right); } }; template struct BIT0based { BIT0based(int n, const Abelian UNITY = 0) : n(n), UNITY(UNITY), dat(n, UNITY) {} void add(int idx, Abelian val) { while (idx < n) { dat[idx] += val; idx |= idx + 1; } } Abelian sum(int idx) { Abelian res = UNITY; --idx; while (idx >= 0) { res += dat[idx]; idx = (idx & (idx + 1)) - 1; } return res; } Abelian sum(int left, int right) { if (right <= left) return UNITY; return sum(right) - sum(left); } Abelian operator[](const int idx) { return sum(idx, idx + 1); } int lower_bound(Abelian val) { if (val <= UNITY) return 0; int res = 0, exponent = 1; while (exponent <= n) exponent <<= 1; for (int mask = exponent >> 1; mask > 0; mask >>= 1) { if (res + mask - 1 < n && dat[res + mask - 1] < val) { val -= dat[res + mask - 1]; res += mask; } } return res; } private: int n; const Abelian UNITY; vector dat; }; int main() { int n; cin >> n; struct Skill { int a, x, b, query; Skill(int a, int b, int c, int query) : a(a), b(b), query(query) { x = b - c; } bool operator<(const Skill &r) { return a != r.a ? a < r.a : x != r.x ? x < r.x : b < r.b; }; }; vector skills; REP(i, n) { int a, b, c; cin >> a >> b >> c; skills.emplace_back(a, b, c, i); } sort(ALL(skills)); // REP(i, n) cout << skills[i].a << ' ' << skills[i].b << ' ' << skills[i].x << '\n'; vector gen(n); REP(i, n) gen[i] = skills[i].a; vector ans(n, LINF); RMQ rmq(n, -LINF); BIT0based bit(n); using P = pair; priority_queue, greater

> que; int border = -1; REP(i, n) { while (!que.empty() && que.top().first < skills[i].a) { int idx = que.top().second; que.pop(); bit.add(idx, -1); int r = upper_bound(ALL(gen), skills[idx].x) - gen.begin(); if (border <= idx && bit.sum(r) == 0) { ans[skills[idx].query] = max(rmq.query(0, r), 0LL) + skills[idx].b; rmq.update(idx, ans[skills[idx].query]); } else { bit.add(idx, 1); } chmax(border, r); } que.emplace(skills[i].x, i); bit.add(i, 1); // REP(i, n) cout << (rmq[i] == -LINF ? -1 : rmq[i]) << " \n"[i + 1 == n]; } while (!que.empty()) { int idx = que.top().second; que.pop(); bit.add(idx, -1); int r = upper_bound(ALL(gen), skills[idx].x) - gen.begin(); if (border <= idx && bit.sum(r) == 0) { ans[skills[idx].query] = max(rmq.query(0, r), 0LL) + skills[idx].b; rmq.update(idx, ans[skills[idx].query]); } chmax(border, r); } // REP(i, n) cout << (rmq[i] == -LINF ? -1 : rmq[i]) << " \n"[i + 1 == n]; REP(i, n) { if (ans[i] == LINF) { cout << "BAN\n"; } else { cout << ans[i] << '\n'; } } return 0; }