#include<bits/stdc++.h> using namespace std; int mod=1e9; long long ANS; set<pair<int,int>>S; queue<array<int,3>>q; void flod(){ while(q.size()) { auto[x,y,d]=q.front(); q.pop(); if(!S.count({x,y}))continue; S.erase({x,y});ANS+=d; q.push({x-1,y,d+1}); q.push({x+1,y,d+1}); q.push({x,y-1,d+1}); q.push({x,y+1,d+1}); } } int DistanceSum(int N, int *X, int *Y) { if(N>2000){ sort(X,X+N); sort(Y,Y+N); long long ans=0; for(long long i=0;i<N;i++){ ans+=i*X[i] - (N-i-1) *X[i]; ans%=mod; } for(long long i=0;i<N;i++){ ans+=i*Y[i] - (N-i-1) *Y[i]; ans%=mod; } return (ans+mod)%mod; } int A=*min_element(Y,Y+N); int B=*min_element(X,X+N); for(int i=0;i<N;i++) S.insert({X[i]-=B,Y[i]-=A}); set<pair<int,int>>st2=S; for(int i=0;i<N;i++){ q.push({X[i],Y[i],0}); flod(); S=st2; } return ANS/2%mod; }