#include using namespace std; #define endl '\n' #define lfs cout<= (ll)(n); i--) using ll = long long; using ld = long double; const ll MOD1 = 1e9+7; const ll MOD9 = 998244353; const ll INF = 1e18; using P = pair; template bool chmin(T &a,T b){if(a>b){a=b;return true;}else return false;} template bool chmax(T &a,T b){if(a void ans(bool x,T1 y,T2 z){if(x)cout< void debug(vector>&v,ll h,ll w){for(ll i=0;i&v,ll h,ll w){for(ll i=0;i void debug(vector&v,ll n){if(n!=0)cout< vector>vec(ll x, ll y, T w){ vector>v(x,vector(y,w));return v;} ll gcd(ll x,ll y){ll r;while(y!=0&&(r=x%y)!=0){x=y;y=r;}return y==0?x:y;} vectordx={1,0,-1,0,1,1,-1,-1}; vectordy={0,1,0,-1,1,-1,1,-1}; template vector make_v(size_t a,T b){return vector(a,b);} template auto make_v(size_t a,Ts... ts){ return vector(a,make_v(ts...)); } template ostream &operator<<(ostream &os, pair&p){ return os << p.first << " " << p.second; } template struct SegmentTree{ using F = function; vector data; ll n,lastlen = 1; T func(T a, T b){return a > b ? a : b;}; bool check (T a, T b){return a >= b;}; T iden = 0; //単位元を変えるのを忘れない!!!!!!!!!! SegmentTree(vector &v){ build(v); } SegmentTree(ll size){ n = size; while(lastlen < n)lastlen *= 2; data.assign(lastlen*2-1,iden); } void build(vector &v){ n = (ll)v.size(); while(lastlen < n)lastlen *= 2; data.assign(lastlen*2-1,iden); for(ll i=0;i=0;i--){ data[i] = func(data[2*i+1], data[2*i+2]); } } void build(){ for(ll i=lastlen-2;i>=0;i--){ data[i] = func(data[2*i+1], data[2*i+2]); } } void update(ll point, T x){ point+=lastlen-1; data[point] = x; while(point!=0){ point=(point-1)/2; data[point]=func(data[2*point+1],data[2*point+2]); } } T query(ll l,ll r){ if(l>=r)return iden; T left = iden, right = iden; l+=lastlen-1, r+=lastlen-1; while(l != r){ if(~l&1)left = func(left, data[l++]); if(~r&1)right = func(data[--r], right); l >>= 1,r >>= 1; } return func(left, right); } T &operator[](ll x){ return data[lastlen-1+x]; } void print(){ for(ll i=0;i=n){ return n; } else{ func(sumbuf,data[p]); p >>= 1; ll x = r + (r-l)*2; l = r; r = x; } } else if(p >= lastlen - 1)return r - 1; else if(!check(func(sumbuf,data[2*p+1]),x)){ sumbuf = func(sumbuf, data[2*p+1]); p = 2*p+2; l = (r+l)/2; } else{ p = 2*p+1; r = (r+l)/2; } } } }; int main(){ cin.tie(nullptr); ios_base::sync_with_stdio(false); ll res=0,buf=0; bool judge = true; ll n;cin>>n; vectora(n),b(n),c(n); rep(i,0,n)cin>>a[i]>>b[i]>>c[i]; vectorvala=a; sort(ALLR(vala)); vectororder(n); iota(ALL(order),0); sort(ALL(order),[&](ll x,ll y){ return max(a[x],b[x]-c[x])>max(a[y],b[y]-c[y]);}); vector

p(n); rep(i,0,n)p[i]=MP(a[i],i); sort(ALLR(p)); SegmentTreeseg(n); SegmentTreesegmx(n); vectoraidx(n); rep(i,0,n)aidx[p[i].se]=i; rep(i,0,n)segmx[aidx[i]]=b[i]-c[i]; segmx.build(); vectorret(n,INF); rrep(i,0,n){ ll t=order[i]; ll idx=lower_bound(ALL(vala),b[t]-c[t],greater())-vala.begin(); ll k=aidx[t]; segmx.update(k,0); if(segmx.query(idx,n)>=a[t]){ ret[t]=INF; } else ret[t]=min(INF,seg.query(idx,n)+b[t]); segmx.update(k,b[t]-c[t]); //cout<