#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <map>
typedef long long llong;
const int MAXN = 100000 + 10;
const int MOD = 1'000'000'000;
int n;
llong ans;
int cnt[MAXN];
int degree[MAXN];
bool isActive[MAXN];
int x[MAXN], y[MAXN];
std::pair <int,int> delta[] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
std::map <std::pair <int,int>, int> map;
std::vector <int> g[MAXN];
std::queue <int> q;
int cntActive;
int DistanceSum(int N, int *X, int *Y)
{
n = N;
cntActive = n;
for (int i = 1 ; i <= n ; ++i)
{
x[i] = X[i - 1];
y[i] = Y[i - 1];
map[{x[i], y[i]}] = i;
}
for (int i = 1 ; i <= n ; ++i)
{
for (const auto &[dx, dy] : delta)
{
if (map.count({x[i] + dx, y[i] + dy}))
{
g[i].push_back(map[{x[i] + dx, y[i] + dy}]);
degree[i]++;
}
}
}
std::fill(isActive + 1, isActive + 1 + n, true);
std::fill(cnt + 1, cnt + 1 + n, 1);
for (int i = 1 ; i <= n ; ++i)
{
if (degree[i] == 1)
{
q.push(i);
}
}
while (!q.empty() && cntActive > 1)
{
int top = q.front();
ans += 1LL * cnt[top] * (n - cnt[top]);
isActive[top] = false;
cntActive--;
q.pop();
for (const int &u : g[top])
{
if (!isActive[u])
{
continue;
}
degree[u]--;
cnt[u] += cnt[top];
if (degree[u] == 1)
{
isActive[u] = false;
q.push(u);
}
}
}
ans %= MOD;
for (int i = 1 ; i <= n ; ++i)
{
for (int j = i + 1 ; j <= n ; ++j)
{
if (isActive[i] && isActive[j])
{
ans += (1LL * (cnt[i] * cnt[j]) % MOD) * (abs(x[i] - x[j]) + abs(y[i] - y[j]));
ans %= MOD;
}
}
}
return ans;
}
