#include <iostream> #include <vector> using namespace std; #define ll long long const int N = 2e5 + 10; const ll INF = 1e17; int n, m; vector <int> add[N], rev[N], queries[N]; struct obj { ll h; int l, r; void inp() { cin >> h >> l >> r; } } a[N]; struct query { int l, r; ll ans; void inp() { cin >> l >> r; ans = -INF; } } q[N]; struct SEG { struct node { ll one, two, val, lazy; node () { one = two = val = lazy = -INF; } } st[N << 2]; void reset() { fill_n(st, N << 2, node()); } void down(int id) { ll lz = st[id].lazy; if (lz == -INF) return; st[id].lazy = -INF; st[id << 1].two = max(st[id << 1].two, lz); st[id << 1].val = st[id << 1].two + st[id << 1].one; st[id << 1].lazy = max(st[id << 1].lazy, lz); st[id << 1 | 1].two = max(st[id << 1 | 1].two, lz); st[id << 1 | 1].val = st[id << 1 | 1].two + st[id << 1 | 1].one; st[id << 1 | 1].lazy = max(st[id << 1 | 1].lazy, lz); } void update_one(int l, int r, int u, ll VAL, int id) { if (l == r) { st[id].one = VAL; st[id].val = st[id].one + st[id].two; return; } int mid = (l + r) >> 1; down(id); if (u <= mid) update_one(l, mid, u, VAL, id << 1); else update_one(mid + 1, r, u, VAL, id << 1 | 1); st[id].one = max(st[id << 1].one, st[id << 1 | 1].one); st[id].val = max(max(st[id << 1].val, st[id << 1 | 1].val), st[id].one + st[id].two); } void update_two(int l, int r, int u, int v, ll VAL, int id) { if (l > v || r < u) return; if (l >= u && r <= v) { st[id].two = max(st[id].two, VAL); st[id].lazy = max(st[id].lazy, VAL); st[id].val = st[id].one + st[id].two; return; } int mid = (l + r) >> 1; down(id); update_two(l, mid, u, v, VAL, id << 1); update_two(mid + 1, r, u, v, VAL, id << 1 | 1); st[id].val = max(max(st[id << 1].val, st[id << 1 | 1].val), st[id].one + st[id].two); } ll get(int l, int r, int u, int v, int id) { if (l > v || r < u) return -INF; if (l >= u && r <= v) return st[id].val; int mid = (l + r) >> 1; down(id); return max(get(l, mid, u, v, id << 1), get(mid + 1, r, u, v, id << 1 | 1)); } } seg; void input() { cin >> n; for (int i = 1; i <= n; ++i) a[i].inp(); cin >> m; for (int i = 1; i <= m; ++i) q[i].inp(); } void LeftToRight() { // reset // seg.reset(); // ------------------ // for (int i = 1; i <= n; ++i) { if (i + a[i].l <= n) add[i + a[i].l].push_back(i); if (i + a[i].r + 1 <= n) rev[i + a[i].r + 1].push_back(i); } for (int i = 1; i <= m; ++i) { queries[q[i].r].push_back(i); } seg.reset(); for (int i = 1; i <= n; ++i) { for (int z: add[i]) seg.update_one(1, n, z, -a[z].h, 1); for (int z: rev[i]) seg.update_one(1, n, z, -INF, 1); int Left = max(1, i - a[i].r), Right = i - a[i].l; if (Left <= Right) { seg.update_two(1, n, Left, Right, a[i].h, 1); } for (int z: queries[i]) { q[z].ans = seg.get(1, n, q[z].l, q[z].r, 1); } } } void RightToLeft() { // reset // seg.reset(); for (int i = 1; i <= n; ++i) { add[i].clear(); rev[i].clear(); queries[i].clear(); } // ------------------ // for (int i = 1; i <= n; ++i) { if (i - a[i].l >= 1) add[i - a[i].l].push_back(i); if (i - a[i].r - 1 >= 1) rev[i - a[i].r - 1].push_back(i); } for (int i = 1; i <= m; ++i) { queries[q[i].l].push_back(i); } seg.reset(); for (int i = n; i >= 1; --i) { for (int z: add[i]) seg.update_one(1, n, z, -a[z].h, 1); for (int z: rev[i]) seg.update_one(1, n, z, -INF, 1); int Left = i + a[i].l, Right = min(n, i + a[i].r); if (Left <= Right) { seg.update_two(1, n, Left, Right, a[i].h, 1); } for (int z: queries[i]) { q[z].ans = max(q[z].ans, seg.get(1, n, q[z].l, q[z].r, 1)); } } } void solve() { LeftToRight(); RightToLeft(); for (int i = 1; i <= m; ++i) { if (q[i].ans < 0) q[i].ans = -1; cout << q[i].ans << "\n"; } } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); input(); solve(); return 0; }