#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000000
int N,X[100001],Y[100001];
int minX=INF,minY=INF;
map<pair<int,int>,int>mp;
vector<int>row[100005],col[100005];
ll ans;
int rt[100005],siz[100005];
void reset(){
for (int i=0;i<N;i++){
rt[i]=i;
siz[i]=1;
}
}
int root(int x){
while (x!=rt[x]){
rt[x]=rt[rt[x]];
x=rt[x];
}
return x;
}
void merge(int a, int b){
a=root(a);
b=root(b);
if (a==b) return;
if (siz[a]<siz[b]) swap(a,b);
rt[b]=a;
siz[a]+=siz[b];
}
void sweepRow(){
reset();
for (int i=1;i<=N;i++){
for (int j:row[i]){
if (X[j]>1 && mp.count({X[j]-1,Y[j]}))
merge(j,mp[{X[j]-1,Y[j]}]);
if (Y[j]>1 && mp.count({X[j],Y[j]-1}))
merge(j,mp[{X[j],Y[j]-1}]);
if (Y[j]<N && mp.count({X[j],Y[j]+1}))
merge(j,mp[{X[j],Y[j]+1}]);
}
set<ll>s;
for (int j:row[i])
s.insert(root(j));
for (ll x:s){
ans+=siz[x]*(N-siz[x]);
}
ans%=MOD;
}
}
void sweepCol(){
reset();
for (int i=1;i<=N;i++){
for (int j:col[i]){
if (X[j]>1 && mp.count({X[j]-1,Y[j]}))
merge(j,mp[{X[j]-1,Y[j]}]);
if (X[j]<N && mp.count({X[j]+1,Y[j]}))
merge(j,mp[{X[j]+1,Y[j]}]);
if (Y[j]>1 && mp.count({X[j],Y[j]-1}))
merge(j,mp[{X[j],Y[j]-1}]);
}
set<ll>s;
for (int j:col[i])
s.insert(root(j));
for (ll x:s){
ans+=siz[x]*(N-siz[x]);
}
ans%=MOD;
}
}
int DistanceSum(int n, int x[], int y[]){
N=n;
for (int i=0;i<N;i++){
X[i]=x[i];
Y[i]=y[i];
minX=min(minX,X[i]);
minY=min(minY,Y[i]);
}
for (int i=0;i<N;i++){
X[i]-=(minX-1);
Y[i]-=(minY-1);
mp[{X[i],Y[i]}]=i;
row[X[i]].push_back(i);
col[Y[i]].push_back(i);
}
sweepRow();
sweepCol();
return ans;
}
