#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define llint long long #define inf 1e18 #define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++) #define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++) #define eps 1e-9 using namespace std; typedef pair P; struct edge{ llint to, cost; edge(){} edge(llint a, llint b){ to = a, cost = b; } }; llint n; llint a[100005], b[100005], c[100005]; P p[100005]; vector G[1<<18], revG[1<<18]; llint N = 1<<17; vector topo; bool used[1<<18]; int scc[1<<18]; map mp; llint dp[1<<18]; llint ans[100005]; void tpsort(int v) { used[v] = true; for(int i = 0; i < G[v].size(); i++){ if(!used[G[v][i].to]) tpsort(G[v][i].to); } topo.push_back(v); } void sccdfs(int v, int id) { used[v] = true; scc[v] = id; for(int i = 0; i < revG[v].size(); i++){ if(!used[revG[v][i].to]) sccdfs(revG[v][i].to, id); } } void add(int a, int b, int k, int l, int r, llint s, llint c) { if(b < l || r < a) return ; if(a <= l && r <= b){ G[s+N].push_back(edge(k, c)); return; } add(a, b, k*2, l, (l+r)/2, s, c); add(a, b, k*2+1, (l+r)/2+1, r, s, c); } void add(int a, int b, llint s, llint c) { if(a > b) return; //cout << a << " " << b << " " << s << " " << c << endl; return add(a, b, 1, 0, N-1, s, c); } void dfs(int v) { used[v] = true; for(int i = 0; i < revG[v].size(); i++){ if(!used[revG[v][i].to]) dfs(revG[v][i].to); } } int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i]; for(int i = 1; i <= n; i++) p[i] = P(a[i], i); sort(p+1, p+n+1); p[0] = P(-inf, 0); for(int i = 0; i < N; i++){ G[i].push_back(edge(i*2, 0)); G[i].push_back(edge(i*2+1, 0)); } for(llint i = 1; i <= n; i++){ llint id = p[i].second; llint pos = upper_bound(p, p+n+1, P(b[id]-c[id], inf)) - p; add(0, min(i-1, pos-1), i, b[id]); add(i+1, pos-1, i, b[id]); } for(int i = 0; i < 2*N; i++){ for(int j = 0; j < G[i].size(); j++){ revG[G[i][j].to].push_back(edge(i, G[i][j].cost)); } } for(int i = 0; i < 2*N; i++) if(!used[i]) tpsort(i); reverse(topo.begin(), topo.end()); int id = 0; for(int i = 0; i < 2*N; i++) used[i] = false; for(int i = 0; i < topo.size(); i++) if(!used[topo[i]]) sccdfs(topo[i], id++); for(int i = 0; i < 2*N; i++) mp[scc[i]]++, used[i] = false;; for(int i = 0; i < 2*N; i++){ if(!used[i] && mp[scc[i]] >= 2) dfs(i); } for(int i = 0; i < 2*N; i++) dp[i] = -inf; dp[N] = 0; reverse(topo.begin(), topo.end()); for(int i = 0; i < topo.size(); i++){ llint v = topo[i]; if(used[v]) continue; for(int j = 0; j < revG[v].size(); j++){ llint u = revG[v][j].to; if(used[u]) continue; dp[u] = max(dp[u], dp[v] + revG[v][j].cost); } } for(int i = 1; i <= n; i++){ llint id = p[i].second; if(used[N+i]) ans[id] = -1; else ans[id] = dp[N+i]; } for(int i = 1; i <= n; i++){ if(ans[i] == -1) cout << "BAN" << endl; else cout << ans[i] << endl; } return 0; }