#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; namespace atcoder{};using namespace atcoder; using ull = uint64_t; using ll = int64_t; using vi = vector; using vll = vector; using vs = vector; using ld = long double; using P = pair; using G = vector>; #ifdef MYDEBUG template string join(const C& c){stringstream ss; for(auto it=c.begin(); it!=c.end();it++){ss << *it;if(it!=c.end())ss<<", ";}return ss.str();} template ostream &operator<<(ostream &os, const vector& c){for(auto it=c.begin(); it!=c.end();it++){os << *it;if(it!=c.end())os<<", ";}return os;} #define LO(...) fprintf(stderr, __VA_ARGS__) #define debug(x) cerr << "\033[33m(line:" << __LINE__ << ") " << #x << ": " << x << "\033[m" << endl #else #define LO(...) (void)0 #define debug(x) (void)0 #endif #define reps(i,a,n) for(ll i##_len = (ll)(n), i = (a); i < i##_len; ++i) #define rep(i,n) reps(i,0,n) #define rrep(i,n) reps(i,1,n+1) #define repd(i,n) for(ll i=n-1;i>=0;i--) #define rrepd(i,n) for(ll i=n;i>=1;i--) #define inp(i) ll i; cin >> i; #define inps(s) string s; cin >> s; #define inpp(p) cin >> (p).first >> (p).second #define inpv(v,N) vll v(N);rep(i,N)cin>>v[i]; #define inpg(g,N,M) g.resize(N);rep(i,M){inp(a);inp(b);a--,b--;g[a].push_back(b);g[b].push_back(a);} #define all(v) begin(v),end(v) #define YESNO(b) cout<<(b?"YES\n":"NO\n") #define yesno(b) cout<<(b?"yes\n":"no\n") #define YesNo(b) cout<<(b?"Yes\n":"No\n") #define YES cout<<"YES\n" #define NO cout<<"NO\n" #define yes cout<<"yes\n" #define no cout<<"no\n" #define Yes cout<<"Yes\n" #define No cout<<"No\n" #define SP cout << " " #define ENDL cout << "\n" #define ou(i) cout << (i) #define ous(i) cout << (i) << " " #define oul(i) cout << (i) << "\n" #define setfp() cout << fixed << setprecision(16) template void ouv(const C &v){for(auto &&e:v){cout << e;if(&e != &v.back()) cout << ' ';}cout << "\n";} template void ouvadd(const C &v){for(auto &&e:v){cout << e+1;if(&e != &v.back()) cout << ' ';}cout << "\n";} templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b #include #include #ifndef ATCODER_INTERNAL_BITOP_HPP #define ATCODER_INTERNAL_BITOP_HPP 1 #ifdef _MSC_VER #include #endif namespace atcoder { namespace internal { // @param n `0 <= n` // @return minimum non-negative `x` s.t. `n <= 2**x` int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } // @param n `1 <= n` // @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0` constexpr int bsf_constexpr(unsigned int n) { int x = 0; while (!(n & (1 << x))) x++; return x; } // @param n `1 <= n` // @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0` int bsf(unsigned int n) { #ifdef _MSC_VER unsigned long index; _BitScanForward(&index, n); return index; #else return __builtin_ctz(n); #endif } } // namespace internal } // namespace atcoder #endif // ATCODER_INTERNAL_BITOP_HPP namespace atcoder { template struct segtree { public: segtree() : segtree(0) {} explicit segtree(int n) : segtree(std::vector(n, e())) {} explicit segtree(const std::vector& v) : _n(int(v.size())) { log = internal::ceil_pow2(_n); size = 1 << log; d = std::vector(2 * size, e()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) const { assert(0 <= p && p < _n); return d[p + size]; } S prod(int l, int r) const { assert(0 <= l && l <= r && r <= _n); S sml = e(), smr = e(); l += size; r += size; while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() const { return d[1]; } template int max_right(int l) const { return max_right(l, [](S x) { return f(x); }); } template int max_right(int l, F f) const { assert(0 <= l && l <= _n); assert(f(e())); if (l == _n) return _n; l += size; S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!f(op(sm, d[l]))) { while (l < size) { l = (2 * l); if (f(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template int min_left(int r) const { return min_left(r, [](S x) { return f(x); }); } template int min_left(int r, F f) const { assert(0 <= r && r <= _n); assert(f(e())); if (r == 0) return 0; r += size; S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!f(op(d[r], sm))) { while (r < size) { r = (2 * r + 1); if (f(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector d; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } }; } // namespace atcoder #endif // ATCODER_SEGTREE_HPP ll op(ll a, ll b){return a+b;} ll e(){return 0;} using SEG = atcoder::segtree; int main(){ inp(N); vll A(N),T(N); rep(i,N)cin>>A[i]>>T[i]; inp(Q); vector> q(Q+N*2); rep(i,Q){ cin >> q[i].first.first >> q[i].second.first >> q[i].second.second; q[i].second.first--; q[i].first.second = i; } rep(i,N){ q[Q+i].first.first = T[i]; q[Q+i].first.second = -3; q[Q+i].second.first = i; q[Q+N+i].first.first = T[i] + A[i]; q[Q+N+i].first.second = -2; q[Q+N+i].second.first = i; } sort(all(q)); SEG fi(N),se(N),ti(N); rep(i,N){ fi.set(i,A[i]); } ll prev_time = 0; vll ans(Q); rep(i,N+N+Q){ auto [a,b] = q[i].first; auto [c,d] = q[i].second; if(b == -3){ se.set(c, 1); ti.set(c, a); }else if(b == -2){ se.set(c, 0); ti.set(c, 0); fi.set(c, 0); }else{ ll tot = fi.prod(c, d); ll count = se.prod(c, d); ll timetot = ti.prod(c, d); debug(a); debug(tot); debug(count); debug(timetot); ans[b] = tot + (timetot - count * (a+1)); } } rep(i,Q){ oul(ans[i]); } return 0; }