#include <bits/stdc++.h> #define ll long long #define fi first #define se second #define pr pair <int, int> using namespace std; const int N = 2e5 + 5; const ll inf = 1e18; struct Seg { ll mmin, mmax, val; }; Seg st[N*4], lazy[N*4]; int n, h[N], L[N], R[N], q; ll ans[N]; vector <pr> event, query[N]; void inp() { cin >> n; for (int i = 1; i <= n; i++) { cin >> h[i] >> L[i] >> R[i]; } for (int i = 1; i <= n; i++) { event.push_back({i + L[i], i}); event.push_back({i + R[i] + 1, -1}); } cin >> q; for (int i = 1; i <= q; i++) { int l, r; cin >> l >> r; query[r].push_back({l, i}); } } void push (int id) { if (lazy[id].mmin != 1e18) { st[id * 2].mmin = min(st[id * 2].mmin, lazy[id].mmin); st[id * 2].mmax = max(st[id * 2].mmax, lazy[id].mmax); st[id * 2].val = st[id * 2].mmax - st[id * 2].mmin; lazy[id * 2].mmin = min(lazy[id * 2].mmin, lazy[id].mmin); lazy[id * 2].mmax = max(lazy[id * 2].mmax, lazy[id].mmax); st[id * 2 + 1].mmin = min(st[id * 2 + 1].mmin, lazy[id].mmin); st[id * 2 + 1].mmax = max(st[id * 2 + 1].mmax, lazy[id].mmax); st[id * 2 + 1].val = st[id * 2 + 1].mmax - st[id * 2 + 1].mmin; lazy[id * 2 + 1].mmin = min(lazy[id * 2 + 1].mmin, lazy[id].mmin); lazy[id * 2 + 1].mmax = max(lazy[id * 2 + 1].mmax, lazy[id].mmax); lazy[id].mmin = 1e18; lazy[id].mmax = -1e18; } } Seg combine (Seg a, Seg b) { Seg tmp; tmp.mmin = min(a.mmin, b.mmin); tmp.mmax = max(a.mmax, b.mmax); tmp.val = max(a.val, b.val); return tmp; } void update (int id, int l, int r, int u, int v, ll val, bool t) { if (u > r || v < l) return; if (u <= l & v >= r) { if (val == -1) { st[id].mmin = 1e18; st[id].mmax = -1e18; st[id].val = -1; lazy[id].mmin = 1e18; lazy[id].mmax = -1e18; } else if (t) { //cout << st[id].mmin << " " << val << "\n"; st[id].val = max({st[id].mmax - val, val - st[id].mmin, st[id].val}); lazy[id].mmin = min(lazy[id].mmin, val); lazy[id].mmax = max(lazy[id].mmax, val); } else { st[id].mmin = min(st[id].mmin, val); st[id].mmax = max(st[id].mmax, val); //st[id].val = -1; // cout << u << " " << val << "\n"; } return; } int mid = (l + r) / 2; push(id); update(id * 2, l, mid, u, v, val, t); update(id * 2 + 1, mid + 1, r, u, v, val, t); st[id] = combine(st[id * 2], st[id * 2 + 1]); } ll get (int id, int l, int r, int u, int v) { //cout << st[id].val << "\n"; if (u > r || v < l) return -inf; if (u <= l && v >= r) return st[id].val; int mid = (l + r) / 2; push(id); return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v)); } void solve() { for (int i = 1; i < N*4; i++) { st[i].mmin = 1e18; st[i].mmax = -1e18; lazy[i].mmin = 1e18; lazy[i].mmax = -1e18; st[i].val = -1; } int j = 0; sort(event.begin(), event.end()); for (int i = 1; i <= n; i++) { while (j < event.size() && event[j].fi <= i) { if (event[j].se == -1) update(1, 1, n, event[j].se, event[j].se, -1, 0); else update(1, 1, n, event[j].se, event[j].se, h[event[j].se], 0); j++; } if (i - L[i] >= 1) { // cout << i << " " << i - R[i] << " " << i - L[i] << "\n"; update(1, 1, n, max(1, i - R[i]), max(1, i - L[i]), h[i], 1); } for (pr j : query[i]) { ll tmp = get(1, 1, n, j.fi, i); // cout << tmp.mmax << " " << tmp.mmin << "\n"; ans[j.se] = tmp; } } for (int i = 1; i <= q; i++) cout << ans[i] << "\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); inp(); solve(); }