/** * code generated by JHelper * More info: https://github.com/AlexeyDmitriev/JHelper * @author */ //@formatter:off #pragma GCC optimize("Ofast") #include using namespace std; //@formatter:off #define rep(i, n) for (int i = 0; i < (n); ++i) #define drep(i, n) for (int i = (n)-1; i >= 0; --i) #define srep(i, s, t) for (int i = s; i < t; ++i) #define rng(a) a.begin(), a.end() #define rrng(a) a.rbegin(), a.rend() using ll = long long; using P = pair; using VI = vector; using VVI = vector; using VVVI = vector; using VVVVI = vector; using VL = vector; using VVL = vector; using VVVL = vector; using VVVVL = vector; using VP = vector

; using VVP = vector>; using VS = vector; using VC = vector; using VVC = vector>; using VD = vector; using VVD = vector>; using VVVD = vector; using I_I = pair; const int INF = (int)1e9 + 10; // int max > 2*10^9 const long long INFL = (ll)2e18 + 10; // ll max > 9*10^18 const int JU_5 = 100000; const int JU_6 = 1000000; const ll JU_9 = 1000000000; const ll JU_18 = JU_9*JU_9; #define YES cout << "YES" << endl #define NO cout << "NO" << endl #define Yes cout << "Yes" << endl #define No cout << "No" << endl template pair operator+(const pair &a, const pair &b) { return make_pair(a.first + b.first, a.second + b.second); } template pair operator-(const pair &a, const pair &b) { return make_pair(a.first - b.first, a.second - b.second); } template pair operator*(const pair &a, const pair &b) { return make_pair(a.first * b.first, a.second * b.second); } template pair operator/(const pair &a, const pair &b) { return make_pair(a.first / b.first, a.second / b.second); } // #define MOD 1000000007 #define MOD 998244353 #define pmod(x,y) ((x%y)+y)%y /********** libs **********/ //@formatter:off // jhelper 用変数 ostream *__cout; istream *__cin; void _init_io(std::istream &cin, std::ostream &cout) { // 入出力高速化用 ios::sync_with_stdio(false); cin.tie(nullptr); // 少数15桁まで出力 cout << std::setprecision(15); // jhelper 用 __cout = &cout; __cin = &cin; } //@formatter:off /* デバッグ用 出力 */ template ostream &operator<<(ostream &os, const deque &vec) { os << "deq["; for (auto v: vec) os << v << ","; os << "]"; return os; } template ostream &operator<<(ostream &os, const set &vec) { os << "{"; for (auto v: vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_set &vec) { os << "{"; for (auto v: vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const multiset &vec) { os << "{"; for (auto v: vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_multiset &vec) { os << "{"; for (auto v: vec) os << v << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const pair &pa) { os << "(" << pa.first << "," << pa.second << ")"; return os; } template ostream &operator<<(ostream &os, const map &mp) { os << "{"; for (auto v: mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } template ostream &operator<<(ostream &os, const unordered_map &mp) { os << "{"; for (auto v: mp) os << v.first << "=>" << v.second << ","; os << "}"; return os; } // print like python // src: https://qiita.com/Lily0727K/items/06cb1d6da8a436369eed ///////////////////////////////////////////////////////// void print() { *__cout << endl; } template void print(Head &&head, Tail &&... tail) { *__cout << head; if (sizeof...(tail) != 0) *__cout << " "; print(forward(tail)...); } template void print(vector &vec) { for (auto &a: vec) { *__cout << a; if (&a != &vec.back()) *__cout << " "; } *__cout << endl; } template void print(vector> &df) { for (auto &vec: df) { print(vec); } } // endl なし void Print() {} template void Print(Head &&head, Tail &&... tail) { *__cout << head; if (sizeof...(tail) != 0) *__cout << " "; Print(forward(tail)...); } template void Print(vector &vec) { for (auto &a: vec) { *__cout << a; if (&a != &vec.back()) *__cout << " "; } } //@formatter:off /* * org: https://atcoder.jp/contests/abc213/submissions/24901856 * jhelper で使用するため, 全部 cin での入力にしている. (現状のレベルでは困らないので) */ template void scan(T& a){ *__cin >> a; } template void scan(vector&); template void scan(pair&); template void scan(vector& a){ for(auto&& i : a) scan(i); } template void scan(pair& p){ scan(p.first); scan(p.second); } template void scan(T (&a)[size]){ for(auto&& i : a) scan(i); } void in(){} template void in(T&... a){ (void)initializer_list{ (scan(a), 0)... }; } #define let_v(type,name,...) vectorname(__VA_ARGS__) #define let_V(type,name,size) vectorname(size);in(name) #define let_vv(type,name,h,...) vector>name(h,vector(__VA_ARGS__)) #define let_VV(type,name,h,w) vector>name(h,vector(w));in(name) #define let_vvv(type,name,h,w,...) vector>>name(h,vector>(w,vector(__VA_ARGS__))) #define let_vvvv(type,name,h,w,x,...) vector>>>name(h,vector>>(w,vector>(x,vector(__VA_ARGS__)))) /* string 入力を vector で受け取るみたいな */ vector let_CharVec() { string s; *__cin >> s; return {s.begin(), s.end()}; } //@formatter:off ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } template bool chmax(T& a, C b) { if (a < b) { a = b; return true; } return false; } template bool chmin(T& a, C b) { if (a > b) { a = b; return true; } return false; } template T sum(const vector& v) { T res = 0; for (size_t i = 0; i < v.size(); ++i) res += v[i]; return res; } template vector> idx_pair(vector &vals) { vector> ans; rep(i, vals.size()) { ans.emplace_back(vals[i], i); } return ans; } template T min(T a, C b) { return a <= b ? a : T(b); } template T max(T a, C b) { return a >= b ? a : T(b); } // add other source // #include "../library/graph/UnionFind.cpp" // https://ei1333.github.io/luzhiled/snippets/structure/segment-tree.html template struct SegmentTree { using F = function; int sz; // 葉の先頭 index になる(サイズは sz*2 を確保) // 蟻本と異なり, ルートは index=1 とする. // ノードの子は i*2, i*2+1 となる. vector seg; const F f; const Monoid M1; /* * n: 要素数 * f: 演算 max, min など * M1:単位元 */ SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) { sz = 1; while (sz < n) sz <<= 1; seg.assign(2 * sz, M1); } void set(int k, const Monoid &x) { seg[k + sz] = x; } /** * セグメント木の構築 */ void build() { // 登りながら更新していく for (int k = sz - 1; k > 0; k--) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } /** * index:k を更新する */ void update(int k, const Monoid &x) { k += sz; seg[k] = x; while (k >>= 1) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } /** * [a, b) の区間を計算. * 左開区間に注意. */ Monoid query(int a, int b) { Monoid L = M1, R = M1; for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) { if (a & 1) L = f(L, seg[a++]); if (b & 1) R = f(seg[--b], R); } return f(L, R); } Monoid operator[](const int &k) const { return seg[k + sz]; } /** * 葉の方向に向かって条件を満たす境界を探す * @tparam C * @param a 条件を満たす事がわかってる頂点の index * @param check チェック関数。この関数の条件を満たす index を返す。 * @param M * @param type find_firstの場合 false, find_last の場合 true * @return */ template int _find_subtree(int a, const C &check, Monoid &M, bool type) { while (a < sz) { Monoid nxt = type ? f(seg[2 * a + type], M) : f(M, seg[2 * a + type]); if (check(nxt)) a = 2 * a + type; else M = nxt, a = 2 * a + 1 - type; } return a - sz; } /** * [a, x) がcheckを満たす最初の要素位置xを返す。 * * check: [a,x] が条件を満たさないような関数を渡す。 */ template int find_first(int a, const C &check) { Monoid L = M1; if (a <= 0) { if (check(f(L, seg[1]))) return _find_subtree(1, check, L, false); return -1; } int b = sz; for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) { // 条件を満たすところまで上にのぼる if (a & 1) { Monoid nxt = f(L, seg[a]); if (check(nxt)) // 下方向に条件を満たすものを探す return _find_subtree(a, check, L, false); L = nxt; ++a; } } return -1; } /** * [x, b) がcheckを満たす最後の要素位置xを返す。 * (半開区間で b は含まないことに注意) * * check: (x, b) が条件を満たさないような関数を渡す */ template int find_last(int b, const C &check) { Monoid R = M1; if (b >= sz) { if (check(f(seg[1], R))) return _find_subtree(1, check, R, true); return -1; } int a = sz; for (b += sz; a < b; a >>= 1, b >>= 1) { if (b & 1) { Monoid nxt = f(seg[--b], R); if (check(nxt)) return _find_subtree(b, check, R, true); R = nxt; } } return -1; } }; // usage // int main() { // int n, Q; // scanf("%d %d", &n, &Q); // SegmentTree< int > seg(n, [](int a, int b) { return min(a, b); }, INT_MAX); // while(Q--) { // int T, X, Y; // scanf("%d %d %d", &T, &X, &Y); // if(T == 0) seg.update(X, Y); // else printf("%d\n", seg.query(X, Y + 1)); // } // } // #include "../library/graph/template.cpp" // utils // #include "../library/mint.cpp" // #include "../library/string/utils.cpp" // #include "../library/math/utils.cpp" /**************************/ struct E{ ll t; int ty; int i; }; class No2101CherryAlphaN { public: void solve(std::istream &cin, std::ostream &cout) { _init_io(cin, cout); int t = 1; // cin >> t; while (t--) _solve(cin, cout); } //@formatter:on void _solve(std::istream &cin, std::ostream &cout) { // code int n; cin >> n; VL a(n), t(n); rep(i, n) { cin >> a[i] >> t[i]; } int Q; cin >> Q; VL d(Q); VI l(Q), r(Q); rep(i, Q) { cin >> d[i] >> l[i] >> r[i]; l[i]--, r[i]--; } vector evs; rep(i, n) { if(a[i]>0) { evs.push_back({t[i], -1, i}); evs.push_back({a[i] + t[i], 0, i}); } } rep(i, Q) { evs.push_back({d[i], 1, i}); } std::sort(evs.begin(), evs.end(), [](E a, E b) { if (a.t == b.t)return a.ty < b.ty; return a.t < b.t; }); using X = int; const X I = 0; SegmentTree seg_cnt(n + 1, [](X a, X b) { return a + b; }, I); using Y = ll; const Y II = 0; SegmentTree seg_t(n + 1, [](Y a, Y b) { return a + b; }, II); SegmentTree seg(n + 1, [](Y a, Y b) { return a + b; }, II); rep(i, n) { seg.set(i, a[i]); } seg.build(); VL ans(Q); for (auto &e: evs) { if (e.ty == 0) { seg.update(e.i, 0); seg_t.update(e.i, 0); seg_cnt.update(e.i, 0); } else if (e.ty == -1) { int idx = e.i; seg_t.update(e.i, -t[idx] + 1); seg_cnt.update(e.i, 1); } else if (e.ty == 1) { int i = e.i; ll tot = seg.query(l[i], r[i] + 1); ll cnt = seg_cnt.query(l[i], r[i] + 1); ll sumt = seg_t.query(l[i], r[i] + 1); // print("chk",i,l[i],r[i]); // print(tot,cnt,sumt); tot -= (cnt * d[i] + sumt); ans[i] = tot; } } rep(i,ans.size())print(ans[i]); } }; int main() { No2101CherryAlphaN solver; std::istream& in(std::cin); std::ostream& out(std::cout); solver.solve(in, out); return 0; }