#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=500, 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<n; i++) a.pb({a1[i], b1[i]});
        for (ll i=0; i<m; i++) b.pb({a2[i], b2[i]});
        vector <ll> num=calc(b, a);
        RMQ S(num);
        for (ll i=1; 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<m; i++) a.pb({a2[i], b2[i]});
        for (ll i=0; i<n; i++) b.pb({a1[i], b1[i]});
        vector <ll> num=calc(b, a);
        RMQ S(num);
        for (ll i=1; 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;
}