#include<bits/stdc++.h> using namespace std; int mod=1e9; long long ANS; bitset<2010>done; queue<pair<int,int>>q; vector<int>adj[2010]; map<pair<int,int>,int>S; void flod(){ while(q.size()) { auto[x,d]=q.front(); q.pop(); if(done[x])continue; done[x]=1;ANS+=d; for(auto i:adj[x]) q.push({i,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[{X[i]-=B,Y[i]-=A}]=i; for(int i=0;i<N;i++){ if(S.count({X[i]-1,Y[i]})) adj[i].push_back(S[{X[i]-1,Y[i]}]); if(S.count({X[i]+1,Y[i]})) adj[i].push_back(S[{X[i]+1,Y[i]}]); if(S.count({X[i],Y[i]-1})) adj[i].push_back(S[{X[i],Y[i]-1}]); if(S.count({X[i],Y[i]+1})) adj[i].push_back(S[{X[i],Y[i]+1}]); } for(int i=0;i<N;i++){ q.push({i,0}); flod(); done.reset(); } return ANS/2%mod; }