#include <iostream> #include <vector> #include <algorithm> using namespace std; const int N = (1<<18) + 1, inf = 1.01e9; int Mx[N<<1], c[N<<1], Lz[N<<1], Ans[N], a[N], b[N], l[N], r[N], h[N], n, q; vector<pair<int, int>> Quer[N], vec; void Push(int cur, int lc, int rc){ Mx[lc] = max(Mx[lc], c[lc] - Lz[cur]), Lz[lc] = min(Lz[lc], Lz[cur]); Mx[rc] = max(Mx[rc], c[rc] - Lz[cur]), Lz[rc] = min(Lz[rc], Lz[cur]); Lz[cur] = inf; } void insert(int i, int vl, int cur = 1, int st = 1, int en = N){ if (i >= en or i < st) return; if (en - st == 1){ c[cur] = vl; return; } int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2; Push(cur, lc, rc); insert(i, vl, lc, st, mid); insert(i, vl, rc, mid, en); c[cur] = max(c[lc], c[rc]); Mx[cur] = max(Mx[cur], max(Mx[lc], Mx[rc])); } void update(int l, int r, int vl, int cur = 1, int st = 1, int en = N){ if (l >= en or r <= st) return; if (l <= st and r >= en){ Mx[cur] = max(Mx[cur], c[cur] - vl); Lz[cur] = min(Lz[cur], vl); return; } int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2; Push(cur, lc, rc); update(l, r, vl, lc, st, mid); update(l, r, vl, rc, mid, en); Mx[cur] = max(Mx[cur], max(Mx[lc], Mx[rc])); } int get(int l, int r, int cur = 1, int st = 1, int en = N){ if (l >= en or r <= st) return 0; if (l <= st and r >= en) return Mx[cur]; int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2; Push(cur, lc, rc); return max(get(l, r, lc, st, mid), get(l, r, rc, mid, en)); } void solve(){ for (int i=1;i<(N<<1);i++) Mx[i] = c[i] = -inf, Lz[i] = inf; vec = {}; for (int i=1;i<=n;i++){ vec.push_back({i + a[i], i}); vec.push_back({i + b[i] + 1, -i}); } sort(rbegin(vec), rend(vec)); for (int i=1;i<=q;i++) Quer[r[i]].push_back({l[i], i}); for (int i=1;i<=n;i++){ while (vec.size() > 0 and vec.back().first == i){ int k = vec.back().second, vl = -inf; vec.pop_back(); if (k > 0) vl = h[k], k = -k; insert(-k, vl); } update(max(0, i - b[i]), max(0, i - a[i] + 1), h[i]); for (auto [L, id] : Quer[i]) Ans[id] = max(Ans[id], get(L, i)); Quer[i] = {}; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n; for (int i=1;i<=n;i++) cin>>h[i]>>a[i]>>b[i]; cin>>q; for (int i=1;i<=q;i++) cin>>l[i]>>r[i]; solve(); for (int i=1;i+i<=n;i++){ swap(h[i], h[n - i + 1]); swap(a[i], a[n - i + 1]); swap(b[i], b[n - i + 1]); } for (int i=1;i<=q;i++) l[i] = n - l[i] + 1, r[i] = n - r[i] + 1, swap(l[i], r[i]); solve(); for (int i=1;i<=q;i++) cout<<Ans[i]<<' '; cout<<'\n'; }