#include "grader.cpp"
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;
const ll maxn=100005, s=1, inf=5e18;
// returns a vector where the ith element is the maximum value when a[i] is paired with one of the elements of b
vector <ll> calc(const vector <pll> &a, const vector <pll> &b)
{
ll n=sz(a), m=sz(b);
vector <ll> ans(n, 0);
auto cost=[&](ll i, ll j) {return (a[i].fi+b[j].fi)*(a[i].se+b[j].se);};
function <void(ll, ll, ll, ll)> DnC=[&](ll l, ll r, ll optl, ll optr)
{
if (l>r) return;
ll mid=(l+r)/2, opt=optl;
for (ll i=optl; i<=optr; i++)
if (ans[mid]<cost(mid, i))
opt=i, ans[mid]=cost(mid, i);
DnC(l, mid-1, opt, optr);
DnC(mid+1, r, optl, opt);
}; DnC(0, n-1, 0, m-1);
return ans;
}
struct RMQ
{
ll n;
vector <ll> num;
vector <vector <ll>> sp;
RMQ(vector <ll> num): num(num)
{
n=sz(num);
sp=vector <vector <ll>>(__lg(n)+1, vector <ll> (n));
for (ll i=0; i<n; i++) sp[0][i]=num[i];
for (ll i=1; i<=__lg(n); i++)
for (ll j=0; j+(1<<i)<=n; j++)
sp[i][j]=max(sp[i-1][j], sp[i-1][j+(1<<i-1)]);
}
ll query(ll l, ll r)
{
l--, r--;
ll j=__lg(r-l+1);
return max(sp[j][l], sp[j][r-(1<<j)+1]);
}
};
vector<long long> build_teams(vector<int> a1, vector<int> b1, vector<int> a2, vector<int> b2,
vector<int> l1, vector<int> r1, vector<int> l2, vector<int> r2)
{
ll n=sz(a1), m=sz(a2), q=sz(l1);
vector <ll> answer(q, 0);
for (ll i=0; i<q; i++)
{
ll bl1=l1[i]/s, br1=r1[i]/s, bl2=l2[i]/s, br2=r2[i]/s;
vector <pll> a, b;
if (bl1==br1) for (ll j=l1[i]; j<=r1[i]; j++) a.pb({a1[j], b1[j]});
else
{
for (ll j=l1[i]; j<(bl1+1)*s; j++) a.pb({a1[j], b1[j]});
for (ll j=br1*s; j<=r1[i]; j++) a.pb({a1[j], b1[j]});
}
if (bl2==br2) for (ll j=l2[i]; j<=r2[i]; j++) b.pb({a2[j], b2[j]});
else
{
for (ll j=l2[i]; j<(bl2+1)*s; j++) b.pb({a2[j], b2[j]});
for (ll j=br2*s; j<=r2[i]; j++) b.pb({a2[j], b2[j]});
}
vector <ll> res1=calc(a, b), res2=calc(b, a);
for (ll j:res1) answer[i]=max(answer[i], j);
for (ll j:res2) answer[i]=max(answer[i], j);
}
for (ll bl=0; bl+s<=n; bl+=s)
{
vector <pll> a, b;
for (ll i=bl; i<bl+s; i++) a.pb({a1[i], b1[i]});
for (ll i=0; i<m; i++) b.pb({a2[i], b2[i]});
RMQ S(calc(b, a));
for (ll i=0; i<q; i++)
if (l1[i]<=bl && bl+s-1<=r1[i])
answer[i]=max(answer[i], S.query(l2[i], r2[i]));
}
for (ll bl=0; bl+s<=m; bl+=s)
{
vector <pll> a, b;
for (ll i=bl; i<bl+s; i++) a.pb({a2[i], b2[i]});
for (ll i=0; i<n; i++) b.pb({a1[i], b1[i]});
RMQ S(calc(b, a));
for (ll i=0; i<q; i++)
if (l2[i]<=bl && bl+s-1<=r2[i])
answer[i]=max(answer[i], S.query(l1[i], r1[i]));
}
return answer;
}