#include using namespace std; using ll=long long; // マクロの定義 #define all(x) x.begin(), x.end() #define len(x) ll(x.size()) #define elif else if #define unless(cond) if (!(cond)) // オーバーロードマクロ #define overload2(_1, _2, name, ...) name #define overload3(_1, _2, _3, name, ...) name #define overload4(_1, _2, _3, _4, name, ...) name #define overload5(_1, _2, _3, _4, _5, name, ...) name // 繰り返し系 #define rep1(n) for (ll i=0; i T floor(T x, U y){return (x>0 ? x/y: (x-y+1)/y);} template T ceil(T x, U y){return (x>0 ? (x+y-1)/y: x/y);} template T mod(T x, U y){ T q=floor(x,y); return x-q*y; } template pair divmod(T x, U y){ T q=floor(x,y); return {q,x-q*y}; } // 指数に関する関数 ll intpow(ll x, ll y){ ll a=1; while (y){ if (y&1) a*=x; x*=x; y>>=1; } return a; } ll modpow(ll x, ll y, ll z){ ll a=1; while (y){ if (y&1) (a*=x)%=z; (x*=x)%=z; y>>=1; } return a; } ll sum(vector &X){ ll y=0; for (auto &&x: X) y+=x; return y; } template T sum(vector &X){ T y=T(0); for (auto &&x: X) y+=x; return y; } // max, min template inline bool chmax(T &a, const U b){ return (a inline bool chmin(T &a, const U b){ return (a>b ? a=b, 1: 0); } template constexpr auto max(T... a){ return max(initializer_list>{a...}); } template constexpr auto min(T... a){ return min(initializer_list>{a...}); } template T max(vector X){ T alpha=X[0]; for (auto x:X) chmax(alpha, x); return alpha; } template T min(vector X){ T alpha=X[0]; for (auto x:X) chmin(alpha, x); return alpha; } // 入出力 template void input(T&... a){(cin >> ... >> a);} void print(){cout << "\n";} template void print(const T& a, const Ts&... b){ cout << a; (cout << ... << (cout << " ", b)); cout << "\n"; } template istream &operator>>(istream &is, pair &P){ is >> P.first >> P.second; return is; } template ostream &operator<<(ostream &os, const pair &P){ os << P.first << " " << P.second; return os; } template vector vector_input(int N, int index){ vector X(N+index); for (int i=index; i> X[i]; return X; } template istream &operator>>(istream &is, vector &X){ for (auto &x: X) is >> x; return is; } template ostream &operator<<(ostream &os, const vector &X){ int N=(int)len(X); rep(i,N) os << (i ? " ": "") << X[i]; return os; } template struct Binary_Indexed_Tree{ int n,log_n,index; vector data; G unit; const function calc; const function inv; // 初期化 public: Binary_Indexed_Tree(int n, const function calc, const G unit, const function inv, const int index): n(n), calc(calc), unit(unit), inv(inv), index(index){ data.assign(n+1,unit); log_n=0; for (; 1<<(log_n+1)<=n; log_n++){} } public: Binary_Indexed_Tree(const vector &vec, const function calc, const G unit, const function inv, const int index): Binary_Indexed_Tree(vec.size(), calc, unit, inv, index){ for (int k=1; k<=n; k++){ data[k]=calc(data[k],vec[k-1]); int l=k+(k&(-k)); if (l<=n) data[l]=calc(data[l], data[k]); } } // 第 k 要素に x を左から加える. void add(int k, G x){ k+=1-index; for (k; k<=n; k+=(k&(-k))) data[k]=calc(data[k], x); } // 第 k 要素を x に変更する. void update(int k ,G x){ add(k, calc(inv((*this)[k]), x)); } // 右半開区間 [index, k) における総和を求める. G sum(int k) const{ k+=-index; if (k<=0) return unit; G y=unit; for (k; k>0; k-=(k&(-k))) y=calc(y, data[k]); return y; } // 右半開区間 [l, r) における総和を求める. G sum(int l, int r) const{ if (l>=r) return unit; else return calc(inv(sum(l)),sum(r)); } // 第 k 要素を取得する. inline G operator[](int k) const {return sum(k,k+1);} int binary_search(function cond){ if (cond(unit)) {return index-1;} int j=0, t=1< A(N), T(N); rep(i,N) input(A[i],T[i]); int Q; input(Q); vector D(Q), L(Q), R(Q); for (int q=0; q; vector Query(Q); for (int q=0; q, greater> E; for (int i=0; i G{ return {x.first+y.first, x.second+y.second}; }; auto neg=[](G x) -> G{ return {-x.first, -x.second}; }; Binary_Indexed_Tree B(N,add,{0,0},neg,0); for (int i=0; i ans(Q); vector mode(N); for(G query: Query){ ll d; int q; tie (d,q)=query; while (!E.empty() && E.top().first<=D[q]){ ll a; int i; tie (a,i)=E.top(); E.pop(); if (mode[i]==0){ B.update(i, {A[i]+T[i]-1, -1}); E.push({A[i]+T[i], i}); }else{ B.update(i, {0,0}); } mode[i]=true; } ll alpha,beta; tie (alpha, beta)=B.sum(L[q],R[q]+1); ans[q]=alpha+beta*D[q]; } for (int q=0; q