#include <bits/stdc++.h> using namespace std; const int maxn = 2e5 + 5; int n, q; int h[maxn], a[maxn], b[maxn]; pair<int, int> queries[maxn]; bool dbg = 0; namespace subtask4 { struct evt { int pos, idx, type; }; struct node { int maxval, minval, best; node(int p1 = 0, int p2 = INT_MAX, int p3 = -1): maxval(p1), minval(p2), best(p3) {} node operator+ (const node &other) { return node(max(maxval, other.maxval), min(minval, other.minval), max(best, other.best)); } }; struct SMT { vector<node> st; vector<pair<int, int>> lz; SMT(int n): st(4*n+5), lz(4*n+5, {0, INT_MAX}) {} // void combine(int id, int l, int r) { // // apply lazy to children, push children // // then merge // } void push(int id, int l, int r) { if (lz[id].first == 0 && lz[id].second == INT_MAX) return ; if (st[id].maxval != 0 && st[id].minval != INT_MAX) { st[id].best = max({st[id].best, abs(lz[id].first-st[id].minval), abs(lz[id].second-st[id].maxval)}); } if (l != r) { if (st[id << 1].maxval != 0 && st[id << 1].minval != INT_MAX) { lz[id << 1].first = max(lz[id << 1].first, lz[id].first); lz[id << 1].second = min(lz[id << 1].second, lz[id].second); // push(id << 1, l, mid); } if (st[id << 1 | 1].maxval != 0 && st[id << 1 | 1].minval != INT_MAX) { lz[id << 1 | 1].first = max(lz[id << 1 | 1].first, lz[id].first); lz[id << 1 | 1].second = min(lz[id << 1 | 1].second, lz[id].second); // push(id << 1 | 1, mid+1, r); } // st[id] = st[id << 1] + st[id << 1 | 1]; } lz[id] = {0, INT_MAX}; } void ptupd(int id, int l, int r, int u, int val) { push(id, l, r); if (l == r) { if (val == 0) { st[id].maxval = 0; st[id].minval = INT_MAX; } else st[id].maxval = st[id].minval = val; return ; } int mid = (l + r) >> 1; if (u <= mid) ptupd(id << 1, l, mid, u, val); else ptupd(id << 1 | 1, mid+1, r, u, val); // if (lz[id << 1].first != 0 || lz[id << 1].second != INT_MAX || lz[id << 1 | 1].first != 0 || lz[id << 1 | 1].second != INT_MAX) { // cerr << "UPDATES NOT PUSHED!!!!!!!\n"; // } push(id << 1, l, mid); push(id << 1 | 1, mid+1, r); st[id] = st[id << 1] + st[id << 1 | 1]; } void rangeupd(int id, int l, int r, int u, int v, int val) { push(id, l, r); if (r < u || l > v) return ; if (u <= l && r <= v) { if (st[id].maxval == 0 && st[id].minval == INT_MAX) return ; lz[id].first = max(lz[id].first, val); lz[id].second = min(lz[id].second, val); push(id, l, r); return ; } int mid = (l + r) >> 1; rangeupd(id << 1, l, mid, u, v, val); rangeupd(id << 1 | 1, mid+1, r, u, v, val); // if (lz[id << 1].first != 0 || lz[id << 1].second != INT_MAX || lz[id << 1 | 1].first != 0 || lz[id << 1 | 1].second != INT_MAX) { // cerr << "UPDATES NOT PUSHED!!!!!!!\n"; // } push(id << 1, l, mid); push(id << 1 | 1, mid+1, r); st[id] = st[id << 1] + st[id << 1 | 1]; } int query(int id, int l, int r, int u, int v) { push(id, l, r); if (r < u || l > v) return -1; if (u <= l && r <= v) { // cout << "at [" << l << ", " << r << "]: " << st[id].best << '\n'; return st[id].best; } int mid = (l + r) >> 1; return max(query(id << 1, l, mid, u, v), query(id << 1 | 1, mid+1, r, u, v)); } }; void solve() { vector<evt> events; vector<pair<pair<int, int>, int>> qe(q); vector<int> ans(q); for (int i = 1; i <= n; ++i) { events.push_back({i, i, 2}); events.push_back({i+a[i], i, 1}); events.push_back({i+b[i]+1, i, 0}); } for (int i = 0; i < q; ++i) { qe[i] = {queries[i+1], i}; } sort(qe.begin(), qe.end(), [](pair<pair<int, int>, int> &p1, pair<pair<int, int>, int> &p2) {return p1.first.second < p2.first.second;}); sort(events.begin(), events.end(), [](evt &e1, evt &e2) {return (e1.pos == e2.pos ? e1.type < e2.type : e1.pos < e2.pos);}); SMT seg(n); int j = 0; for (int i = 0; i < q; ++i) { while (j < events.size() && events[j].pos <= qe[i].first.second) { //upd seg int idx = events[j].idx, type = events[j].type; if (dbg) cerr << events[j].pos << ' ' << idx << ' ' << type << '\n'; if (type == 0) { if (dbg) cerr << "deactivating node " << idx << '\n'; seg.ptupd(1, 1, n, idx, 0); } else if (type == 1) { if (dbg) cerr << "activating node " << idx << '\n'; seg.ptupd(1, 1, n, idx, h[idx]); } else { if (idx-a[idx] >= 1) { if (dbg) cerr << "updating nodes [" << max(1, idx-b[idx]) << ", " << idx-a[idx] << "]\n"; seg.rangeupd(1, 1, n, max(1, idx-b[idx]), idx-a[idx], h[idx]); } else if (dbg) cerr << "skipping this update (" << idx-a[idx] << " < 1)\n"; } // if (dbg) { // cerr << "current tree: "; // for (int k = 1; k <= n; ++k) cerr << seg.query(1, 1, n, k, k) << ' '; // cerr << '\n'; // } ++j; } // cout << seg.query(1, 1, n, qe[i].first.first, qe[i].first.second) << ' ' << seg.query(1, 1, n, qe[i].first.first, qe[i].first.second) << '\n'; int answer = seg.query(1, 1, n, qe[i].first.first, qe[i].first.second); if (dbg) cerr << "query " << '#' << qe[i].second << " at [" << qe[i].first.first << ", " << qe[i].first.second << "]: " << answer << "\n"; ans[qe[i].second] = answer;// range maximium/minimum query; } for (auto i : ans) cout << i << '\n'; } } int main() { ios::sync_with_stdio(false); cin.tie(0); // freopen("in.INP", "r", stdin); // freopen("o.OUT", "w", stdout); 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 >> queries[i].first >> queries[i].second; // if (subtask12::check()) subtask12::solve(); // else if (subtask3::check()) subtask3::solve(); subtask4::solve(); return 0; }