#include using namespace std; #define int long long templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b> graph(500010); vector seg; using UnWeightedGraph = vector< vector< int > >; int num[500010]; int n; template< typename G > struct StronglyConnectedComponents { const G &g; UnWeightedGraph gg, rg; vector< int > comp, order, used; StronglyConnectedComponents(G &g) : g(g), gg(g.size()), rg(g.size()), comp(g.size(), -1), used(g.size()) { for(int i = 0; i < g.size(); i++) { for(auto e : g[i]) { gg[i].emplace_back((int) e); rg[(int) e].emplace_back(i); } } } int operator[](int k) { return comp[k]; } void dfs(int idx) { if(used[idx]) return; used[idx] = true; for(int to : gg[idx]) dfs(to); order.push_back(idx); } void rdfs(int idx, int cnt) { if(comp[idx] != -1) return; comp[idx] = cnt; for(int to : rg[idx]) rdfs(to, cnt); } void build(UnWeightedGraph &t) { for(int i = 0; i < gg.size(); i++) dfs(i); reverse(begin(order), end(order)); int ptr = 0; for(int i : order) if(comp[i] == -1) rdfs(i, ptr), ptr++; t.resize(ptr); for(int i = 0; i < g.size(); i++) { for(auto &to : g[i]) { int x = comp[i], y = comp[to]; if(x == y) continue; t[x].push_back(y); } } } }; int size; int init(int n){ int sz = n; size = 1; while(size < sz) size *= 2; int si = n; seg.resize(2*size); for(int i = 0;i < size;i++){ seg[i+size-1] = si; if(i < n) graph[si].push_back(i); si++; } for(int i = size-2;i >= 0;i--){ seg[i] = si; graph[si].push_back(seg[i*2+1]); graph[si].push_back(seg[i*2+2]); si++; } return si; } void add_edge(int a, int b, int num, int k=0, int l=0, int r=size){ if(r <= a || b <= l) return; if(a <= l && r <= b) { graph[num].push_back(seg[k]); return; } add_edge(a, b, num, 2*k+1, l, (l+r)/2); add_edge(a, b, num, 2*k+2, (l+r)/2, r); } vector> ngraph; int cnt[1000010]; int memo[1000010]; int dp(int idx){ if(cnt[idx] > 2){ return LLONG_MAX; } if(memo[idx] != -1) return memo[idx]; int ans = num[idx]; for(int i = 0;i < ngraph[idx].size();i++){ int tmp = dp(ngraph[idx][i]); if(tmp == LLONG_MAX) return memo[idx] = tmp; ans = max(ans, tmp+num[idx]); } return memo[idx] = ans; } signed main(){ cin >> n; vector>> p, konbo; vector aa; int all_n = init(n); for(int i = 0;i < n;i++){ int a, b, c; cin >> a >> b >> c; p.push_back({a, {b, c}}); konbo.push_back({a, {b, c}}); aa.push_back(a); } sort(p.begin(), p.end()); sort(aa.begin(), aa.end()); for(int i = 0;i < n;i++){ int idx = upper_bound(aa.begin(), aa.end(), p[i].second.first-p[i].second.second) - aa.begin(); if(idx <= i){ add_edge(0, idx, i); }else{ add_edge(0, i, i); add_edge(i+1, idx, i); } } StronglyConnectedComponents>> kyo(graph); kyo.build(ngraph); for(int i = 0;i < all_n;i++){ cnt[kyo[i]]++; } for(int i = 0;i < n;i++){ int idx = lower_bound(p.begin(), p.end(), konbo[i]) - p.begin(); num[kyo[idx]] = p[idx].second.first; } memset(memo, -1, sizeof(memo)); for(int i = 0;i < n;i++){ int idx = lower_bound(p.begin(), p.end(), konbo[i]) - p.begin(); int ans = dp(kyo[idx]); if(ans == LLONG_MAX){ cout << "BAN" << endl; }else{ cout << ans << endl; } } return 0; }