#include <bits/stdc++.h> using namespace std; #define __Master_Moon__ int main() #define ll long long #define el "\n" #define base 300 #define fi first #define sq(x) (x)*(x) #define se second #define pub push_back #define puf push_front #define pii pair <int, int> #define pll pair <long long, long long> #define piii pair <long long, pair <int, int>> #define iiii pair <int, pair <int, pair <int, int>>> #define plll pair <long long, pair <long long, long long>> #define FOR(i, a, b) for(int i = (a);i <=(b);i++) #define FO(i, a, b) for(int i = (a);i >= (b);i--) #define REP(i, n) for(int i = 0;i < (n);i++) long const maxn = 5e5 + 50; struct hung { int maxH,minH,res; int lazymaxH,lazyminH; } st[4*maxn]; int n,m,H[maxn],ans[maxn]; pii range[maxn]; vector<int> in[maxn],out[maxn]; vector<pii> q[maxn]; void down(int id) { if(st[id].lazymaxH != INT_MIN) { if(st[id*2].maxH != INT_MIN) { int tmp = max(abs(st[id*2].maxH - st[id].lazymaxH),abs(st[id*2].minH - st[id].lazymaxH)); int mtp = max(abs(st[id*2].maxH - st[id].lazyminH),abs(st[id*2].minH - st[id].lazyminH)); st[id*2].res = max({st[id*2].res,tmp,mtp}); } if(st[id*2+1].maxH != INT_MIN) { int tmp = max(abs(st[id*2+1].maxH - st[id].lazymaxH),abs(st[id*2+1].minH - st[id].lazymaxH)); int mtp = max(abs(st[id*2+1].maxH - st[id].lazyminH),abs(st[id*2+1].minH - st[id].lazyminH)); st[id*2+1].res = max({st[id*2+1].res,tmp,mtp}); } st[id*2].lazymaxH = max(st[id*2].lazymaxH,st[id].lazymaxH); st[id*2].lazyminH = min(st[id*2].lazyminH,st[id].lazyminH); st[id*2+1].lazymaxH = max(st[id*2+1].lazymaxH,st[id].lazymaxH); st[id*2+1].lazyminH = min(st[id*2+1].lazyminH,st[id].lazyminH); st[id].lazymaxH = INT_MIN; st[id].lazyminH = INT_MAX; } } void update(int l,int r,int pos,int val,int id) { if(l > pos || r < pos) return; if(l == r) { if(val == -1) { st[id].maxH = INT_MIN; st[id].minH = INT_MAX; } else st[id].maxH = st[id].minH = H[l]; return; } down(id); int mid = (l+r)/2; update(l,mid,pos,val,id*2); update(mid+1,r,pos,val,id*2+1); st[id].maxH = max(st[id*2].maxH,st[id*2+1].maxH); st[id].minH = min(st[id*2].minH,st[id*2+1].minH); st[id].res = max({st[id*2].res,st[id*2+1].res,st[id].res}); } void uprng(int l,int r,int u,int v,int val,int id) { if(l > v || r < u) return; if(l >= u && r <= v) { if(st[id].maxH != INT_MIN) { int tmp = max(abs(st[id].maxH - val),abs(st[id].minH - val)); st[id].res = max(st[id].res,tmp); } st[id].lazymaxH = max(st[id].lazymaxH,val); st[id].lazyminH = min(st[id].lazyminH,val); return; } down(id); int mid = (l+r)/2; uprng(l,mid,u,v,val,id*2); uprng(mid+1,r,u,v,val,id*2+1); st[id].maxH = max(st[id*2].maxH,st[id*2+1].maxH); st[id].minH = min(st[id*2].minH,st[id*2+1].minH); st[id].res = max({st[id*2].res,st[id*2+1].res,st[id].res}); } int get(int l,int r,int u,int v,int id) { if(l > v || r < u) return -1; if(l >= u && r <= v) return st[id].res; down(id); int mid = (l+r)/2; return max(get(l,mid,u,v,id*2),get(mid+1,r,u,v,id*2+1)); } void solve() { cin >> n; FOR(i,1,n) { int A,B; cin >> H[i] >> A >> B; range[i] = {A,B}; in[i+A].pub(i); out[i+B+1].pub(i); } cin >> m; FOR(i,1,m) { int l,r; cin >> l >> r; q[r].pub({l,i}); } FOR(id,1,4*n) { st[id].maxH = INT_MIN; st[id].minH = INT_MAX; st[id].res = -1; } FOR(i,1,n) { for(int x : in[i]) update(1,n,x,1,1); for(int x : out[i]) update(1,n,x,-1,1); int l = max(1,i - range[i].se),r = i - range[i].fi; uprng(1,n,l,r,H[i],1); for(pii x : q[i]) ans[x.se] = get(1,n,x.fi,i,1); } FOR(i,1,m) cout << ans[i] << el; } __Master_Moon__ { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); solve(); return 0; }