#include using namespace std; using lint = long long int; using pint = pair; using plint = pair; struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_; #define ALL(x) (x).begin(), (x).end() #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i=i##_begin_;i--) #define REP(i, n) FOR(i,0,n) #define IREP(i, n) IFOR(i,0,n) template void ndarray(vector &vec, int len) { vec.resize(len); } template void ndarray(vector &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); } template bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; } template bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; } template pair operator+(const pair &l, const pair &r) { return make_pair(l.first + r.first, l.second + r.second); } template pair operator-(const pair &l, const pair &r) { return make_pair(l.first - r.first, l.second - r.second); } template istream &operator>>(istream &is, vector &vec){ for (auto &v : vec) is >> v; return is; } template ostream &operator<<(ostream &os, const vector &vec){ os << "["; for (auto v : vec) os << v << ","; os << "]"; return os; } template ostream &operator<<(ostream &os, const deque &vec){ os << "deq["; for (auto v : vec) os << v << ","; os << "]"; return os; } template ostream &operator<<(ostream &os, const set &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_set &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const multiset &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_multiset &vec){ os << "{"; for (auto v : vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const pair &pa){ os << "(" << pa.first << "," << pa.second << ")"; return os; } template ostream &operator<<(ostream &os, const map &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_map &mp){ os << "{"; for (auto v : mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } #define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl; /* #include #include #include using namespace __gnu_pbds; // find_by_order(), order_of_key() template using pbds_set = tree, rb_tree_tag, tree_order_statistics_node_update>; template using pbds_map = tree, rb_tree_tag, tree_order_statistics_node_update>; */ constexpr lint INF = 1e18; // Nonrecursive Segment Tree (point-update, range-get) // - Conditions for operations: // - datamerge: [TDATA, TDATA] -> TDATA, e(x, y) == e(y, x) // - data2ret: [TDATA, TQUERY] -> TRET // - retmerge: [TRET, TRET] -> TRET, g(defaultRET, x) == x, g(x, y) = g(y, x) // - commutability f(e(x, y), q) == g(f(x, q), f(y, q)) template struct NonrecursiveSegmentTree { int N; TRET defaultRET; virtual TDATA datamerge(const TDATA &, const TDATA &) = 0; virtual TRET data2ret(const TDATA &, const TQUERY &) = 0; virtual TRET retmerge(const TRET &, const TRET &) = 0; std::vector data; inline TDATA& at(int i) { return data[i]; } inline void _merge(int i) { at(i) = datamerge(at(i << 1), at((i << 1) + 1)); } void initialize(const std::vector &seq, TRET RET_ZERO) { N = seq.size(); defaultRET = RET_ZERO; data = seq; data.insert(data.end(), seq.begin(), seq.end()); for (int i = N - 1; i; i--) _merge(i); } NonrecursiveSegmentTree() = default; void update(int pos, const TDATA &x) { assert(pos >= 0 and pos < N); at(pos + N) = x; for (int i = pos + N; i > 1;) i >>= 1, _merge(i); } // [l, r), 0-indexed TRET get(int l, int r, TQUERY query = NULL) { assert(l >= 0 and r <= N); TRET retl = defaultRET, retr = defaultRET; l += N, r += N; while (l < r) { if (l & 1) retl = retmerge(retl, data2ret(data[l++], query)); if (r & 1) retr = retmerge(data2ret(data[--r], query), retr); l >>= 1, r >>= 1; } return retmerge(retl, retr); } template friend std::ostream &operator<<(std::ostream &os, NonrecursiveSegmentTree s) { os << "[SegmentTree (len: " << s.N << ')'; for (int i = 0; i < s.N; i++) os << s.at(i + s.N) << ','; os << "]"; return os; } }; // Range Maximum Query // - get: return max(x_l, ..., x_{r - 1}) template struct RangeMaximumQuery : public NonrecursiveSegmentTree { using SegTree = NonrecursiveSegmentTree; T datamerge(const T &vl, const T &vr) override { return std::max(vl, vr); }; T data2ret(const T &v, const bool &q) override { return v; } T retmerge(const T &vl, const T &vr) override { return std::max(vl, vr); }; RangeMaximumQuery(const std::vector &seq, T defaultmax) : SegTree::NonrecursiveSegmentTree() { SegTree::initialize(seq, defaultmax); }; }; int main() { int N; cin >> N; vector A(N), B(N), G(N); REP(i, N) { lint a, b, c; cin >> a >> b >> c; A[i] = a; B[i] = b - c; G[i] = b; } vector> a2bi(N); REP(i, N) a2bi[i] = make_pair(A[i], plint(B[i], i)); sort(ALL(a2bi)); vector nx(N); REP(i, N) nx[i] = a2bi[i].second.first; RangeMaximumQuery rmq(nx, -1.2e9); vector nxnx(N); REP(j, N) { lint r = lower_bound(ALL(a2bi), make_pair(a2bi[j].second.first + 1, plint(-1, -1))) - a2bi.begin(); lint hi; if (j < r) hi = max(rmq.get(0, j), rmq.get(j + 1, r)); else hi = rmq.get(0, r); nxnx[a2bi[j].second.second] = hi; } vector ret(N); lint infhi = INF; REP(i, N) if (nxnx[i] >= A[i]) ret[i] = INF, chmin(infhi, A[i]); a2bi.clear(); map pos2gv; pos2gv[-INF] = 0; REP(i, N) { if (B[i] >= infhi) ret[i] = INF; else a2bi.emplace_back(A[i], pint(B[i], i)); } sort(ALL(a2bi)); for (auto p : a2bi) { lint a = p.first; lint b = p.second.first; lint i = p.second.second; auto itr = pos2gv.upper_bound(b); lint gain = G[i] + prev(itr)->second; ret[p.second.second] = gain; chmax(pos2gv[a], gain); itr = pos2gv.lower_bound(a); while (next(itr) != pos2gv.end() and next(itr)->second < itr->second) { pos2gv.erase(next(itr)); itr = pos2gv.lower_bound(a); } if (prev(itr)->second > itr->second) pos2gv.erase(itr); // dbg(ret); } for (auto x : ret) { if (x < INF) printf("%lld\n", x); else puts("BAN"); } }