def Binit(B,siz): while len(B)siz+1: del B[-1] for i in range(siz+1): B[i]=0 B.append(siz) def Badd(B,a,x): z=a while z<=B[-1]: B[z]+=x z+=(z&(-z)) def Bsum(B,a): r=0 z=a while z>0: r+=B[z] z-=(z&(-z)) return r from copy import * def init(N,node,A,unit,func): while len(node): del node[-1] n=1 while n1: y=y>>1 node[y-1]=node[(y<<1)-1]+node[y<<1] def query(node,l,r): x,y=l,r z=node[-1]-1 rr=node[-2] rl=node[-2] while True: if x==y: return rl+rr if x&1: rl=rl+node[x+z] x+=1 if y&1: rr=node[y+z-1]+rr if z==0: return rl+rr x>>=1 y>>=1 z>>=1 mod=10**9+7 def comp(x): #y=sorted(set(x)) y=sorted(x) d=dict() for i in range(len(y)): d[y[i]]=i return d def solve(A,B): N=len(A) X=[(A[i]<<31)+B[i] for i in range(N)] X.sort() X=[(X[i]>>31,X[i]&((1<<31)-1)) for i in range(N)] Y=[X[i][0]-X[i][1] for i in range(N)] Z=[X[i][0]+X[i][1] for i in range(N)] y,z=comp(Y),comp(Z) ANS=0 segy=[] segz=[] Binit(segy,N+3) Binit(segz,N+3) c=0 for i in range(N): if i and X[i]==X[i-1]: c+=1 else: c=0 a,b=y[Y[i]],z[Z[i]] ANS=(ANS+X[i][0]*(Bsum(segy,a)+Bsum(segz,b)-i+c))%mod Badd(segy,a+1,1) Badd(segz,b+1,1) Binit(segy,N+3) Binit(segz,N+3) c=0 for i in range(N-1,-1,-1): if i+1