#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag, tree_order_statistics_node_update>; #define ll long long #define pi pair<int,int> #define vi vector<int> #define pb push_back #define all(a) a.begin(),a.end() const int inf = 1e9; struct Node{ int h,H,d; Node(int h = -inf, int H = -inf, int d = -inf):h(h),H(H),d(d){;} Node operator +(const Node &o) const{ Node res; res.h = max(h,o.h); res.d = max(d,o.d); return res; } }; struct SegTree{ vector<Node> st; int sz; SegTree(int n): st((n<<2)),sz(n){;} void apply(int i, int H){ st[i].d = max(st[i].d,H+st[i].h); st[i].H = max(st[i].H,H); } void push(int i){ if(st[i].H != -inf){ apply(i<<1,st[i].H); apply(i<<1|1,st[i].H); st[i].H = -inf; } } void update(int i, int l, int r, int k, int val){ if(l==r){ if(val) st[i].h = val; else st[i].h = -inf; return; } int m = (l+r)>>1; push(i); if(k <= m) update(i<<1,l,m,k,val); else update(i<<1|1,m+1,r,k,val); st[i] = st[i<<1] + st[i<<1|1]; } void update(int k, int val){ update(1,1,sz,k,val); } void update2(int i, int l, int r, int s, int e, int val){ if(r < s || l > e) return; if(s <= l && r <= e){apply(i,val); return;} int m = (l+r)>>1; push(i); update2(i<<1,l,m,s,e,val); update2(i<<1|1,m+1,r,s,e,val); st[i] = st[i<<1] + st[i<<1|1]; } void update2(int l, int r, int val){ update2(1,1,sz,l,r,val); } int get(int i, int l, int r, int s, int e){ if(r < s || l > e) return -inf; if(s <= l && r <= e) return st[i].d; int m = (l+r)>>1; push(i); return max(get(i<<1,l,m,s,e),get(i<<1|1,m+1,r,s,e)); } int get(int l, int r){ return get(1,1,sz,l,r); } }; const int mxn = 2e5+1; int arr[mxn][3], res[mxn]; vector<pi> qu[mxn], vec[mxn]; void solve(){ int n,q; cin >> n; for(int i = 1; i <= n; i++) cin >> arr[i][0] >> arr[i][1] >> arr[i][2]; cin >> q; for(int i = 1; i <= q; i++){ int l,r; cin >> l >> r; qu[r].push_back({i,l}); } SegTree st(n), st2(n); for(int i = 1; i <= n; i++){ for(auto [j,val] : vec[i]){ st.update(j,-val); st2.update(j,val); } int l = max(1,i-arr[i][2]); int r = i-arr[i][1]; if(l <= r){ st.update2(l,r,arr[i][0]); st2.update2(l,r,-arr[i][0]); } for(auto [j,l] : qu[i]) res[j] = max(st.get(l,i),st2.get(l,i)); if(i + arr[i][1] <= n) vec[i+arr[i][1]].push_back({i,arr[i][0]}); if(i + arr[i][2] + 1 <= n) vec[i+arr[i][2]+1].push_back({i,0}); } for(int i = 1; i <= q; i++) cout << max(-1,res[i]) << '\n'; } signed main(){ cin.tie(0)->sync_with_stdio(0); int t = 1; // cin >> t; while(t--){solve();} }