#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; constexpr lint INF = 2e18; // 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); }; }; // Directed graph library to find strongly connected components (強連結成分分解) // 0-indexed directed graph // Complexity: O(V + E) struct DirectedGraphSCC { int V; // # of Vertices std::vector> to, from; std::vector used; // Only true/false std::vector vs; std::vector cmp; int scc_num = -1; DirectedGraphSCC(int V = 0) : V(V), to(V), from(V), cmp(V) {} void _dfs(int v) { used[v] = true; for (auto t : to[v]) if (!used[t]) _dfs(t); vs.push_back(v); } void _rdfs(int v, int k) { used[v] = true; cmp[v] = k; for (auto t : from[v]) if (!used[t]) _rdfs(t, k); } void add_edge(int from_, int to_) { assert(from_ >= 0 and from_ < V and to_ >= 0 and to_ < V); to[from_].push_back(to_); from[to_].push_back(from_); } // Detect strongly connected components and return # of them. // Also, assign each vertex `v` the scc id `cmp[v]` (0-indexed) int FindStronglyConnectedComponents() { used.assign(V, false); vs.clear(); for (int v = 0; v < V; v++) if (!used[v]) _dfs(v); used.assign(V, false); scc_num = 0; for (int i = (int)vs.size() - 1; i >= 0; i--) if (!used[vs[i]]) _rdfs(vs[i], scc_num++); return scc_num; } // After calling `FindStronglyConnectedComponents()`, generate a new graph by uniting all vertices // belonging to the same component(The resultant graph is DAG). DirectedGraphSCC GenerateTopologicalGraph() { DirectedGraphSCC newgraph(scc_num); for (int s = 0; s < V; s++) for (auto t : to[s]) { if (cmp[s] != cmp[t]) newgraph.add_edge(cmp[s], cmp[t]); } return newgraph; } }; int main() { int N; cin >> N; vector A(N), B(N), G(N); vector Z; REP(i, N) { lint a, b, c; cin >> a >> b >> c; A[i] = a; B[i] = b - c; G[i] = b; Z.push_back(A[i]); Z.push_back(B[i]); } sort(ALL(Z)); Z.erase(unique(ALL(Z)), Z.end()); REP(i, N) { A[i] = lower_bound(ALL(Z), A[i]) - Z.begin(); B[i] = lower_bound(ALL(Z), B[i]) - Z.begin(); } 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]); map pos2gv; pos2gv[-INF] = 0; REP(i, N) { if (B[i] >= infhi) ret[i] = INF; } vector> b2ai(N); REP(i, N) b2ai[i] = make_pair(min(B[i], A[i]), plint(A[i], i)); sort(ALL(b2ai)); REP(j, b2ai.size()) { lint i = b2ai[j].second.second; if (ret[i] >= INF) continue; lint a = A[i]; lint b = B[i]; auto itr = pos2gv.upper_bound(b); lint gain = G[i] + prev(itr)->second; ret[i] = 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); } for (auto x : ret) { if (x < INF) printf("%lld\n", x); else puts("BAN"); } }