class Binary_Indexed_Tree(): def __init__(self, L, calc, unit, inv, index=1): """ calc を演算とする N 項の Binary Indexed Tree を作成 calc: 演算 (2変数関数, 可換群) unit: 群 calc の単位元 (x+e=e+x=xを満たすe) inv : 群 calc の逆元 (1変数関数, x+inv(x)=inv(x)+x=e をみたす inv(x)) """ self.calc=calc self.unit=unit self.inv=inv self.index=index N=len(L) d=max(1,(N-1).bit_length()) k=2**d X=[None]+[unit]*k self.num=k self.depth=d if L: for i in range(len(L)): p=i+1 while p<=k: X[p]=self.calc(X[p],L[i]) p+=p&(-p) self.data=X def index_number(self, k, index=1): """ 第 k 要素の値を出力する. k : 数列の要素 index: 先頭の要素の番号 """ return self.sum(k,k,index) def add(self, k, x, index=1): """ 第 k 要素に x を加え, 更新を行う. k : 数列の要素 x : 加える値 index: 先頭の要素の番号 """ data=self.data; calc=self.calc p=k+(1-index) while p<=self.num: data[p]=calc(self.data[p],x) p+=p&(-p) def update(self, k, x, index=1): """ 第 k 要素を x に変え, 更新を行う. k: 数列の要素 x: 更新後の値 """ a=self.index_number(k,index) y=self.calc(self.inv(a),x) self.add(k,y,index) def sum(self, From, To, index=1): """ 第 From 要素から第 To 要素までの総和を求める. ※From!=1を使うならば, 群でなくてはならない. From : 始まり To : 終わり index: 先頭の要素の番号 """ alpha=max(1,From+(1-index)) beta=min(self.num,To+(1-index)) if alpha>beta: return self.unit elif alpha==1: return self.__section(beta) else: return self.calc(self.inv(self.__section(alpha-1)),self.__section(beta)) def __section(self,x): """ B[1]+...+B[x] を求める. """ data=self.data; calc=self.calc S=self.unit while x>0: S=calc(data[x],S) x-=x&(-x) return S def all_sum(self): return self.data[-1] def binary_search(self, cond, index=1): """ cond(B[1]+...+B[k]) を満たす最小の k を返す. cond: 単調増加 ※ cond(unit)=True の場合の返り値は index-1 ※ cond(B[1]+...+B[k]) なる k が存在しない場合の返り値は self.num+index """ if cond(self.unit): return index-1 j=0 r=self.num t=r data=self.data; calc=self.calc alpha=self.unit for _ in range(self.depth+1): if j+t<=self.num: beta=calc(alpha,data[j+t]) if not cond(beta): alpha=beta j+=t t>>=1 return j+index def __getitem__(self,index): if isinstance(index,int): return self.index_number(index,self.index) else: return [self.index_number(t,self.index) for t in index] def __setitem__(self,index,val): self.update(index,val,self.index) #================================================== from heapq import heapify,heappush,heappop from operator import add,neg import sys input=sys.stdin.readline write=sys.stdout.write #================================================== #入力 N=int(input()) A=[0]*N; T=[0]*N for i in range(N): A[i],T[i]=map(int,input().split()) Q=int(input()) D=[0]*Q; L=[0]*Q; R=[0]*Q for q in range(Q): D[q],L[q],R[q]=map(int,input().split()) L[q]-=1; R[q]-=1 #================================================== # 準備 Query=sorted(range(Q), key=lambda j:D[j]) E=[(T[i],i) for i in range(N)] heapify(E) #================================================== # 本計算 B0=Binary_Indexed_Tree(A.copy(), add, 0, neg, 0) B1=Binary_Indexed_Tree([0]*N, add, 0, neg, 0) Ans=[0]*Q Mode=[0]*N for q in Query: while bool(E) and E[0][0]<=D[q]: a,i=heappop(E) if Mode[i]==0: B0[i]=A[i]+T[i]-1 B1[i]=-1 heappush(E,(A[i]+T[i],i)) else: B0[i]=0 B1[i]=0 Mode[i]+=1 Ans[q]=B1.sum(L[q],R[q],0)*D[q]+B0.sum(L[q],R[q],0) write("\n".join(map(str,Ans)))