#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100001;
int ax[MAXN], ay[MAXN];
const int MOD = 1000000000;
long long solve(vector<int> arr)
{
// build prefix
int sz = arr.size();
long long pref[sz+1];
fill(pref, pref + sz + 1, 0);
for (int i = sz - 1; i >= 0; i--)
{
pref[i] = arr[i] + pref[i + 1];
}
long long inc_pref[sz+1];
fill(inc_pref, inc_pref + sz + 1, 0);
for (int i = sz - 1; i >= 0; i--)
{
inc_pref[i] = pref[i] + inc_pref[i+1];
}
long long ans = 0;
for (int i = 0; i < sz; i++)
{
ans += (long long) arr[i] * (long long) inc_pref[i + 1];
}
return ans;
}
int DistanceSum(int N, int *X, int *Y)
{
// given our grid we can build a stack of nodes at each occupied x and y value.
int startx = INT_MAX, starty = INT_MAX;
for (int i = 0; i < N; i++)
{
startx = min(startx, X[i]);
starty = min(starty, Y[i]);
ax[X[i]]++;
ay[Y[i]]++;
}
// loop over each cell that is stacked and create a list of nodes
int cur = startx;
vector<int> listx;
while (ax[cur])
{
listx.push_back(ax[cur]);
cur++;
}
cur = starty;
vector<int> listy;
while (ay[cur])
{
listy.push_back(ay[cur]);
cur++;
}
long long ans = (solve(listx) + solve(listy)) % MOD;
return ans;
}
// WHEN SUBMITTING PROGRAMMES WITH A METHOD SIGNATURE -> USE MAIN TO TEST
//int main()
//{
// int n;
//
// freopen("input.txt", "r", stdin);
//
// cin >> n;
//
// int x[n];
// int y[n];
//
// for (int i = 0; i < n; i++)
// {
// cin >> x[i] >> y[i];
// }
//
// cout << DistanceSum(n, x, y) << "\n";
//
// return 0;
//}
