#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pll; #define X first #define Y second const ll MAXN = 1e6 + 10; const ll MOD = 1000000000; int n; vector<pll> vec; int DistanceSum(int N, int *X, int *Y) { n = N; sort(X, X + n); sort(Y, Y + n); ll ps = 0, ans = 0; for (int i = 0; i < n; i++) { ans = (ans + (1ll * i * X[i] - ps + MOD)) % MOD; ps = ps + X[i] % MOD; } ps = 0; for (int i = 0; i < n; i++) { ans = (ans + (1ll * i * Y[i] - ps + MOD)) % MOD; ps = ps + Y[i] % MOD; } return ans % MOD; }