import sys readline = sys.stdin.buffer.readline from operator import itemgetter def compress(L): N = len(L) L2 = sorted([N*L[i]+i for i in range(N)]) C = {v : k for k, v in enumerate(L2)} return [C[N*L[i]+i] for i in range(N)] class Segtree: def __init__(self, A, intv, initialize = True, segf = max): self.N = len(A) self.N0 = 2**(self.N-1).bit_length() self.intv = intv self.segf = segf if initialize: self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N) for i in range(self.N0-1, 0, -1): self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) else: self.data = [intv]*(2*self.N0) def update(self, k, x): k += self.N0 self.data[k] = x while k > 0 : k = k >> 1 self.data[k] = self.segf(self.data[2*k], self.data[2*k+1]) def query(self, l, r): L, R = l+self.N0, r+self.N0 s = self.intv while L < R: if R & 1: R -= 1 s = self.segf(s, self.data[R]) if L & 1: s = self.segf(s, self.data[L]) L += 1 L >>= 1 R >>= 1 return s def get(self, x): return self.data[self.N0+x] INF = 10**18 N = int(readline()) ABC = [tuple(map(int, readline().split())) for _ in range(N)] IdxABD = [(i, a, b, b-c) for i, (a, b, c) in enumerate(ABC)] IdxABD.sort(key = itemgetter(3)) Idx, A, B, D = map(list, zip(*IdxABD)) cA = compress(A) sA = sorted(A) aord = [None]*N for j in range(N): aord[cA[j]] = j left = [None]*N for j in range(N): ng = -1 ok = N aj = A[j] while abs(ok-ng) > 1: med = (ok+ng)//2 if D[med] >= aj: ok = med else: ng = med left[j] = ok right = [None]*N for j in range(N): ok = -1 ng = N dj = D[j] while abs(ok-ng) > 1: med = (ok+ng)//2 if sA[med] <= dj: ok = med else: ng = med right[j] = ng atable = Segtree(A, INF, initialize = True, segf = min) valtable = Segtree([0]*N, 0, initialize = False, segf = max) vt = [0]*N Ans = [None]*N ans = [None]*N seen = 0 maxval = 0 for j in range(N): pj = aord[j] ansidx = Idx[pj] if left[pj] <= pj: atable.update(pj, INF) mina = atable.query(left[pj], N) atable.update(pj, A[pj]) else: mina = atable.query(left[pj], N) res = B[pj] if mina <= D[pj]: res = INF inval = False for k in range(seen, left[pj]): if k == pj: inval = True continue elif cA[k] < j: valtable.update(cA[k], ans[k]) else: valtable.update(cA[k], B[k] + maxval) if cA[pj] < right[pj]: cnt = valtable.get(cA[pj]) valtable.update(cA[pj], 0) res = max(res, B[pj] + valtable.query(0, right[pj])) if inval: valtable.update(cA[pj], res) else: valtable.update(cA[pj], cnt) else: res = max(res, B[pj] + valtable.query(0, right[pj])) if inval: valtable.update(cA[pj], res) maxval = max(maxval, res) ans[pj] = res seen = left[pj] if res >= INF: Ans[ansidx] = 'BAN' else: Ans[ansidx] = str(res) print('\n'.join(Ans))