#include <algorithm>
#include <vector>
#include <map>
#define MOD 1000000000
using namespace std;
typedef pair <int,int> ppair;
map <ppair,int> Map1;
map <ppair,int> Map2;
map <ppair,int> :: iterator it;
vector <int> B[100000];
pair <int,int> A[100000];
int N, M, GroupNum[1000000], GroupSize[1000000], Check[1000000];
long long Ans;
void TheyAreGroup(int Left, int Right)
{
int i;
for(i=Left ; i<=Right ; i++)
{
Map1.insert(make_pair(make_pair(A[i].first,A[i].second),M));
GroupNum[i]=M;
}
GroupSize[M]=Right-Left+1;
M++;
}
void MakeGroup(void)
{
int i, j;
for(i=0 ; i<M ; i++)
{
Check[i]=0;
B[i].clear();
}
M=0;
Map1.clear();
Map2.clear();
for(i=0 ; i<N ; i++)
{
for(j=i ; j<N ; j++)
{
if(i!=j && (A[j].first!=A[j-1].first || A[j].second!=A[j-1].second+1))
{
TheyAreGroup(i,j-1);
i=j-1;
break;
}
}
if(j==N)
{
TheyAreGroup(i,N-1);
break;
}
}
for(i=0 ; i<N ; i++)
{
it=Map1.find(make_pair(A[i].first+1,A[i].second));
if(it!=Map1.end())
if(Map2.find(make_pair(GroupNum[i],it->second))==Map2.end())
{
Map2.insert(make_pair(make_pair(GroupNum[i],it->second),0));
Map2.insert(make_pair(make_pair(it->second,GroupNum[i]),0));
B[GroupNum[i]].push_back(it->second);
B[it->second].push_back(GroupNum[i]);
}
it=Map1.find(make_pair(A[i].first-1,A[i].second));
if(it!=Map1.end())
if(Map2.find(make_pair(GroupNum[i],it->second))==Map2.end())
{
Map2.insert(make_pair(make_pair(GroupNum[i],it->second),0));
Map2.insert(make_pair(make_pair(it->second,GroupNum[i]),0));
B[GroupNum[i]].push_back(it->second);
B[it->second].push_back(GroupNum[i]);
}
}
}
int TreeDP(int Now)
{
int i, j=B[Now].size(), Sum=0;
for(i=0 ; i<j ; i++)
if(!Check[B[Now][i]])
{
Check[B[Now][i]]=1;
Sum+=TreeDP(B[Now][i]);
}
Sum+=GroupSize[Now];
Ans+=(long long)Sum*((long long)N-(long long)Sum);
Ans%=MOD;
return Sum;
}
int DistanceSum(int N_, int *X, int *Y)
{
int i, temp;
N=N_;
for(i=0 ; i<N ; i++)
A[i]=make_pair(X[i],Y[i]);
sort(A,A+N);
MakeGroup();
Check[0]=1;
temp=TreeDP(0);
for(i=0 ; i<N ; i++)
A[i]=make_pair(Y[i],X[i]);
sort(A,A+N);
MakeGroup();
Check[0]=1;
temp=TreeDP(0);
return Ans;
}
