WA #3 #9

#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
    char c=getchar();
    int f=1,x=0;
    while(c>'9'||c<'0'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
void write(int x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
int n,m,q;
//int bmin=INT_MAX,bmax=INT_MIN;
int a[100010],b[100010];
struct Node{
    int l,r,maxn_z,minn_z,maxn_f,minn_f,zero;
}t[400010],t1[400010];
struct Type{
    int maxn_z,minn_z,maxn_f,minn_f,zero;
};
void build1(int p,int l,int r){
    t[p].l=l,t[p].r=r;
    if(l==r){
        if(a[l]>0){
            t[p].maxn_z=t[p].minn_z=a[l];
            t[p].maxn_f=INT_MIN,t[p].minn_f=INT_MAX;
        }
        else if(a[l]<0){
            t[p].maxn_f=t[p].minn_f=a[l];
            t[p].maxn_z=INT_MIN,t[p].minn_z=INT_MAX;
        }
        else{
            t[p].zero=1;
            t[p].maxn_f=INT_MIN,t[p].minn_f=INT_MAX;
            t[p].maxn_z=INT_MIN,t[p].minn_z=INT_MAX;
        }
        return;
    }
    int mid=(l+r)/2;
    build1(p*2,l,mid);
    build1(p*2+1,mid+1,r);
    t[p].maxn_z=max(t[p*2].maxn_z,t[p*2+1].maxn_z);
    t[p].maxn_f=max(t[p*2].maxn_f,t[p*2+1].maxn_f);
    t[p].minn_z=min(t[p*2].minn_z,t[p*2+1].minn_z);
    t[p].minn_f=min(t[p*2].minn_f,t[p*2+1].minn_f);
    t[p].zero=(t[p*2].zero||t[p*2+1].zero);
}
Type search1(int p,int l,int r){
    Type ret;
    if(l<=t[p].l&&r>=t[p].r){
        ret.maxn_z=t[p].maxn_z;
        ret.minn_z=t[p].minn_z;
        ret.maxn_f=t[p].maxn_f;
        ret.minn_f=t[p].minn_f;
        ret.zero=t[p].zero;
        return ret;
    }
    int mid=(t[p].l+t[p].r)/2,f1=0,f2=0;
    Type ret1,ret2;
    if(l<=mid){
        f1=1;
        ret1=search1(p*2,l,r);
    }
    if(r>mid){
        f2=1;
        ret2=search1(p*2+1,l,r);
    }
    if(f1&&f2){
        ret.maxn_z=max(ret1.maxn_z,ret2.maxn_z);
        ret.maxn_f=max(ret1.maxn_f,ret2.maxn_f);
        ret.minn_z=min(ret1.minn_z,ret2.minn_z);
        ret.minn_f=min(ret1.minn_f,ret2.minn_f);
        ret.zero=(ret1.zero||ret2.zero);
        return ret;
    }
    if(f1)return ret1;
    if(f2)return ret2;
}
void build2(int p,int l,int r){
    t1[p].l=l,t1[p].r=r;
    if(l==r){
        if(b[l]>0){
            t1[p].maxn_z=t1[p].minn_z=b[l];
            t1[p].maxn_f=INT_MIN,t1[p].minn_f=INT_MAX;
        }
        else if(b[l]<0){
            t1[p].maxn_f=t1[p].minn_f=b[l];
            t1[p].maxn_z=INT_MIN,t1[p].minn_z=INT_MAX;
        }
        else{
            t1[p].zero=1;
            t1[p].maxn_f=INT_MIN,t1[p].minn_f=INT_MAX;
            t1[p].maxn_z=INT_MIN,t1[p].minn_z=INT_MAX;
        }
        return;
    }
    int mid=(l+r)/2;
    build2(p*2,l,mid);
    build2(p*2+1,mid+1,r);
    t1[p].maxn_z=max(t1[p*2].maxn_z,t1[p*2+1].maxn_z);
    t1[p].maxn_f=max(t1[p*2].maxn_f,t1[p*2+1].maxn_f);
    t1[p].minn_z=min(t1[p*2].minn_z,t1[p*2+1].minn_z);
    t1[p].minn_f=min(t1[p*2].minn_f,t1[p*2+1].minn_f);
    t1[p].zero=(t1[p*2].zero||t1[p*2+1].zero);
}
Type search2(int p,int l,int r){
    Type ret;
    if(l<=t1[p].l&&r>=t1[p].r){
        ret.maxn_z=t1[p].maxn_z;
        ret.minn_z=t1[p].minn_z;
        ret.maxn_f=t1[p].maxn_f;
        ret.minn_f=t1[p].minn_f;
        ret.zero=t1[p].zero;
        return ret;
    }
    int mid=(t1[p].l+t1[p].r)/2,f1=0,f2=0;
    Type ret1,ret2;
    if(l<=mid){
        f1=1;
        ret1=search2(p*2,l,r);
    }
    if(r>mid){
        f2=1;
        ret2=search2(p*2+1,l,r);
    }
    if(f1&&f2){
        ret.maxn_z=max(ret1.maxn_z,ret2.maxn_z);
        ret.maxn_f=max(ret1.maxn_f,ret2.maxn_f);
        ret.minn_z=min(ret1.minn_z,ret2.minn_z);
        ret.minn_f=min(ret1.minn_f,ret2.minn_f);
        ret.zero=(ret1.zero||ret2.zero);
        return ret;
    }
    if(f1)return ret1;
    if(f2)return ret2;
}
signed main(){
    //freopen("game.in","r",stdin);
    //freopen("game.out","w",stdout);
    n=read(),m=read(),q=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    for(int i=1;i<=m;i++){
        b[i]=read();
    }
    build1(1,1,n);
    build2(1,1,m);
    while(q--){
        int l1=read(),r1=read(),l2=read(),r2=read();
        Type L=search1(1,l1,r1),Q=search2(1,l2,r2);
        //cerr<<L.maxn_z<<" "<<L.minn_z<<" "<<L.maxn_f<<" "<<L.minn_f<<" "<<L.zero<<"\n";
        //cerr<<Q.maxn_z<<" "<<Q.minn_z<<" "<<Q.maxn_f<<" "<<Q.minn_f<<" "<<Q.zero<<"\n";
        int f1=(L.maxn_z!=INT_MIN&&Q.maxn_f==INT_MIN);//i have Z,but y have not F
        int f2=(L.maxn_f!=INT_MIN&&Q.maxn_z==INT_MIN);//i have F,but y have not Z
        if(f1&&f2){
            cout<<max(L.maxn_z*Q.minn_z,L.minn_f*Q.maxn_f)<<endl;
        }
        else if(f1){
            cout<<L.maxn_z*Q.minn_z<<endl;
        }
        else if(f2){
            cout<<L.minn_f*Q.maxn_f<<endl;
        }
        else{
            if(L.zero)cout<<0<<endl;
            else if(L.minn_z==INT_MAX&&Q.minn_f==INT_MAX){
            	cout<<L.maxn_f*Q.maxn_z<<endl;
            }
            else if(L.minn_f==INT_MAX&&Q.minn_z==INT_MAX){
            	cout<<L.minn_z*Q.minn_f<<endl;
            }
            else cout<<max(L.minn_z*Q.minn_f,L.maxn_f*Q.maxn_z)<<endl;
        }
    }
    return 0;
}