WA #3 #9 #16

#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);
		//cout<<L.maxn_z<<" "<<L.minn_z<<" "<<L.maxn_f<<" "<<L.minn_f<<" "<<L.zero<<"\n";
		//cout<<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 cout<<max(L.minn_z*Q.minn_f,L.maxn_f*Q.maxn_z)<<endl;
		}
	}
	return 0;
}