#include <bits/stdc++.h>
using namespace std;
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define ll long long
const int mod = 1e9;
int add(int a, int b) {
a += b;
if(a > mod) {
a -= mod;
}
return a;
}
int mul(int a, int b) {
a = (ll)a * b % mod;
return a;
}
int sub(int a, int b) {
a -= b;
if(a < 0) {
a += mod;
}
return a;
}
vector<pair<int, int>> dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
int DistanceSum(int n, int *X, int *Y) {
// ans = sum(abs(x[i] - x[j])) + sum(abs(y[i] - y[j])) treat cases
vector<int> x;
int suff_x = 0;
for(int i = 0; i < n; ++i) {
x.push_back(X[i]);
suff_x = add(suff_x, X[i]);
}
int suff_y = 0;
vector<int> y;
for(int i = 0; i < n; ++i) {
y.push_back(Y[i]);
suff_y = add(suff_y, Y[i]);
}
sort(x.begin(), x.end());
sort(y.begin(), y.end());
int ans = 0;
for(int i = 0; i < n; ++i) {
ans = add(ans, sub(suff_x, mul((n - i), x[i])));
suff_x = sub(suff_x, x[i]);
ans = add(ans, sub(suff_y, mul((n - i), y[i])));
suff_y = sub(suff_y, y[i]);
}
return ans;
}
