#pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-fhoist-adjacent-loads") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #include using namespace std; const long long INF = 2000000001; const long long MOD = 1000000007; //https://judge.yosupo.jp/submission/81486 template > struct FenwickTree1D { int N; vector BIT; Op op; FenwickTree1D(int N, T qdef = T(), Op op = Op()) : N(N), BIT(N + 1, qdef), op(op) {} template FenwickTree1D(int N, F f, T qdef = T(), Op op = Op()) : FenwickTree1D(N, qdef, op) { for (int i = 1; i <= N; i++) { BIT[i] = op(BIT[i], f()); int j = i + (i & -i); if (j <= N) BIT[j] = op(BIT[j], BIT[i]); } } template FenwickTree1D(It st, It en, T qdef = T(), Op op = Op()) : FenwickTree1D( en - st, [&] { return *st++; }, qdef, op) { } template > vector values(Inv inv = Inv()) { vector ret(BIT.begin() + 1, BIT.end()); for (int i = N; i >= 1; i--) { int j = i + (i & -i); if (j <= N) ret[j - 1] = inv(ret[j - 1], ret[i - 1]); } return ret; } void update(int i, T v) { for (i++; i <= N; i += i & -i) BIT[i] = op(BIT[i], v); } T query(int r) { T ret = BIT[0]; for (r++; r > 0; r -= r & -r) ret = op(ret, BIT[r]); return ret; } template > T query(int l, int r, Inv inv = Inv()) { return inv(query(r), query(l - 1)); } template int bsearch(T v, F cmp) { T agg = BIT[0]; int ind = 0; for (int j = __lg(N + 1); j >= 0; j--) { int i = ind + (1 << j); if (i <= N && cmp(op(agg, BIT[i]), v)) agg = op(agg, BIT[ind = i]); } return ind; } }; // add (x, y, v) // query [x1, x2] x [y1, y2] struct Query { int t, xlo, xhi, ylo, yhi, v; Query(int t, int xlo, int xhi, int ylo, int yhi, int v) : t(t), xlo(xlo), xhi(xhi), ylo(ylo), yhi(yhi), v(v) {} }; void add_point(vector& queries, int x, int y, int v) { queries.push_back(Query(0, x, x, y, y, v)); } void add_query(vector& queries, int l, int r, int d, int u) { queries.push_back(Query(1, l, r - 1, d, u - 1, 0)); } struct Event { int t, x, ylo, yhi, v; Event(int t, int x, int ylo, int yhi, int v) : t(t), x(x), ylo(ylo), yhi(yhi), v(v) {} bool operator<(const Event &e) const { return make_pair(x, t) < make_pair(e.x, e.t); } }; vector solve(vector queries) { vector events; events.reserve(queries.size() * 2); vector YS; YS.reserve(queries.size()); for (auto &&q : queries) if (q.t == 0) YS.push_back(q.ylo); sort(YS.begin(), YS.end()); YS.erase(unique(YS.begin(), YS.end()), YS.end()); int qcnt = 0; for (auto &&q : queries) { if (q.t == 0) q.ylo = lower_bound(YS.begin(), YS.end(), q.ylo) - YS.begin(); else { q.ylo = lower_bound(YS.begin(), YS.end(), q.ylo) - YS.begin(); q.yhi = int(upper_bound(YS.begin(), YS.end(), q.yhi) - YS.begin()) - 1; q.v = qcnt++; if (q.ylo > q.yhi) q.t = -1; } } vector ans(qcnt, 0); FenwickTree1D FT(YS.size()); function rec = [&](int l, int r) { if (l == r) return; int m = l + (r - l) / 2; rec(l, m); rec(m + 1, r); events.clear(); for (int i = l; i <= m; i++) if (queries[i].t == 0) events.emplace_back(0, queries[i].xlo, queries[i].ylo, queries[i].ylo, queries[i].v); if (events.empty()) return; int curSize = events.size(); for (int i = m + 1; i <= r; i++) if (queries[i].t == 1) { events.emplace_back(-1, queries[i].xlo, queries[i].ylo, queries[i].yhi, queries[i].v); events.emplace_back(1, queries[i].xhi, queries[i].ylo, queries[i].yhi, queries[i].v); } if (curSize == int(events.size())) return; sort(events.begin(), events.end()); for (auto &&e : events) { if (e.t == 0) FT.update(e.ylo, e.v); else ans[e.v] += e.t * FT.query(e.ylo, e.yhi); } for (auto &&e : events) if (e.t == 0) FT.update(e.ylo, -e.v); }; if (qcnt > 0) rec(0, int(queries.size()) - 1); return ans; } int main(){ int N; cin >> N; vector a(N); for (int i = 0; i < N; i++){ cin >> a[i]; } vector b(N); for (int i = 0; i < N; i++){ cin >> b[i]; } vector ans(2, 0); for (int i = 0; i < 2; i++){ vector> P(N); for (int j = 0; j < N; j++){ P[j] = make_pair(a[j], b[j]); } sort(P.begin(), P.end()); for (int j = 0; j < N; j++){ a[j] = P[j].first; b[j] = P[j].second; } vector> P2(N); for (int j = 0; j < N; j++){ P2[j] = make_pair(b[j], j); } sort(P2.begin(), P2.end()); vector id(N); for (int j = 0; j < N; j++){ id[j] = P2[j].second; } vector q1, q2; for (int j = 0; j < N; j++){ int p = id[j]; add_query(q1, 0, p, -INF, a[p] - b[p]); add_query(q2, p + 1, N, a[p] + b[p] + 1, INF); add_point(q1, p, a[p] - b[p], 1); add_point(q2, p, a[p] + b[p], 1); } for (int j = 0; j < N; j++){ add_point(q1, j, a[j] - b[j], -1); add_point(q2, j, a[j] + b[j], -1); } for (int j = N - 1; j >= 0; j--){ int p = id[j]; add_query(q2, 0, p, -INF, a[p] + b[p]); add_query(q1, p + 1, N, a[p] - b[p] + 1, INF); add_point(q1, p, a[p] - b[p], 1); add_point(q2, p, a[p] + b[p], 1); } vector ans1 = solve(q1); vector ans2 = solve(q2); for (int j = 0; j < N; j++){ int p = id[j]; ans[i] += (long long) a[p] * ans1[j] % MOD; ans[i] += MOD - (long long) a[p] * ans2[j] % MOD; ans[i] += (long long) a[p] * ans2[N * 2 - 1 - j] % MOD; ans[i] += MOD - (long long) a[p] * ans1[N * 2 - 1 - j] % MOD; } ans[i] %= MOD; ans[i] += MOD; ans[i] *= 2; ans[i] %= MOD; swap(a, b); } cout << ans[0] << ' ' << ans[1] << endl; }