#include #define rep(i,a,b) for(int i=a;i=b;i--) #define fore(i,a) for(auto &i:a) #define all(x) (x).begin(),(x).end() //#pragma GCC optimize ("-O3") using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); } typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60; templatebool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; } templatebool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; } //--------------------------------------------------------------------------------------------------- /*---------------------------------------------------------------------------------------------------             ∧_∧       ∧_∧  (´<_` )  Welcome to My Coding Space!      ( ´_ゝ`) /  ⌒i @hamayanhamayan0     /   \    | |     /   / ̄ ̄ ̄ ̄/  |   __(__ニつ/  _/ .| .|____      \/____/ (u ⊃ ---------------------------------------------------------------------------------------------------*/ struct DirectedGraphRangeEdge { int NV; vector> E; void init(int n) { NV = 1; while (NV < n) NV *= 2; E.resize(NV * 2); rep(i, 1, NV) { E[i].push_back(i * 2); E[i].push_back(i * 2 + 1); } } // [x, y) void add(int from, int x, int y) { add(from + NV, x, y, 0, NV, 1); } void add(int from, int x, int y, int l, int r, int k) { if (r <= x || y <= l) return; if (x <= l && r <= y) { E[from].push_back(k); return; } add(from, x, y, l, (l + r) / 2, k * 2); add(from, x, y, (l + r) / 2, r, k * 2 + 1); } }; int N; DirectedGraphRangeEdge dgre; vector> ABCi; ll ans[101010]; //--------------------------------------------------------------------------------------------------- ll memo[1 << 19]; // -1: not visited -2: pending 0<=: cached infl: BAN ll dfs(int cu) { if (0 <= memo[cu]) return memo[cu]; if (memo[cu] == -2) return memo[cu] = infl; memo[cu] = -2; ll res = 0; fore(to, dgre.E[cu]) chmax(res, dfs(to)); if (res == infl) return infl; if (dgre.NV <= cu) res += get<1>(ABCi[cu - dgre.NV]); return memo[cu] = res; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; dgre.init(N); rep(i, 0, N) { int a, b, c; cin >> a >> b >> c; ABCi.push_back(make_tuple(a, b, c, i)); } sort(all(ABCi)); rep(i, 0, N) { int b, c, _; tie(_, b, c, _) = ABCi[i]; int idx = lower_bound(all(ABCi), make_tuple(b - c + 1, -1, -1, -1)) - ABCi.begin(); if (i < idx) { if (0 < i) dgre.add(i, 0, i); if (i + 1 < idx) dgre.add(i, i + 1, idx); } else dgre.add(i, 0, idx); } rep(i, 0, 1 << 19) memo[i] = -1; rep(i, 0, N) ans[get<3>(ABCi[i])] = dfs(i + dgre.NV); rep(i, 0, N) { if (ans[i] == infl) printf("BAN\n"); else printf("%lld\n", ans[i]); } }