//#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005, M = 1000000000;
const int xx[4] = {0, 1, 0, -1};
const int yy[4] = {1, 0, -1, 0};
ll ans;
int n;
int X[N], Y[N];
map<pair<int, int>, int> mp;
int k;
int c[N];
void dfs(int i)
{
if (c[i])
return;
c[i] = k;
if (mp.find(m_p(X[i], Y[i] + 1)) != mp.end())
dfs(mp[m_p(X[i], Y[i] + 1)]);
if (mp.find(m_p(X[i], Y[i] - 1)) != mp.end())
dfs(mp[m_p(X[i], Y[i] - 1)]);
}
int q[N];
vector<int> g[N];
void dfs1(int x, int p)
{
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i];
if (h == p)
continue;
dfs1(h, x);
q[x] += q[h];
}
ans += (q[x] * 1LL * (n - q[x]));
}
void solv()
{
k = 0;
memset(c, 0, sizeof c);
for (int i = 0; i < n; ++i)
g[i].clear();
memset(q, 0, sizeof q);
for (int i = 0; i < n; ++i)
{
if (!c[i])
{
++k;
dfs(i);
}
}
for (int i = 0; i < n; ++i)
{
if (mp.find(m_p(X[i] + 1, Y[i])) != mp.end())
{
g[c[i]].push_back(c[mp[m_p(X[i] + 1, Y[i])]]);
g[c[mp[m_p(X[i] + 1, Y[i])]]].push_back(c[i]);
}
}
for (int i = 0; i < n; ++i)
{
sort(all(g[i]));
vector<int> v;
for (int j = 0; j < sz(g[i]); ++j)
{
if (!j || g[i][j] != g[i][j - 1])
v.push_back(g[i][j]);
}
g[i] = v;
}
for (int i = 0; i < n; ++i)
{
q[c[i]]++;
}
dfs1(1, 1);
}
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];
}
int minx = X[0];
int miny = Y[0];
for (int i = 0; i < n; ++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);
}
for (int i = 0; i < n; ++i)
{
mp[m_p(X[i], Y[i])] = i;
}
solv();
mp.clear();
for (int i = 0; i < n; ++i)
{
swap(X[i], Y[i]);
mp[m_p(X[i], Y[i])] = i;
}
solv();
return (ans % M);
}
