#include using namespace std; #define int long long struct SegmentTree { private: int n; vector node; public: SegmentTree(vector v) { int sz = (int)v.size(); n = 1; while(n < sz) n *= 2; node.resize(2*n-1, 0); for(int i=0; i=0; i--) node[i] = node[i*2+1] + node[i*2+2]; } void add(int k, int val) { k += (n - 1); node[k] += val; while(k > 0) { k = (k - 1) / 2; node[k] = node[2*k+1] + node[2*k+2]; } } int getsum(int a, int b, int k=0, int l=0, int r=-1) { if(r < 0) r = n; if(b <= l || r <= a) return 0; if(a <= l && r <= b) return node[k]; int vl = getsum(a, b, 2*k+1, l, (l+r)/2); int vr = getsum(a, b, 2*k+2, (l+r)/2, r); return vl + vr; } }; signed main(){ int N; cin>>N; vector A(N),T(N); priority_queue,vector>,greater>> pq; SegmentTree s(vector(N,0)); SegmentTree t(vector(N,0)); for(int i=0;i>A[i]>>T[i]; pq.push({T[i],i}); s.add(i,A[i]); } int q; cin>>q; vector> Q(q); vector a(q); for(int i=0;i>a>>b>>c; Q[i] = {a,b-1,c,i}; } sort(Q.begin(),Q.end()); for(int z=0;z