#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read(){
	ll p=0,o=1;char c=getchar();
	while(c>'9'||c<'0'){if(c=='-')o=-1;c=getchar();}
	while(c<='9'&&c>='0'){p=p*10+c-'0';c=getchar();}
	return p*o;
}
ll a,s,d[3005],f[3005],g;
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	a=read(),s=read();
	if(a<=5){
		for(int i=1;i<=s;i++)d[i]=read();
		for(int i=1;i<=s;i++)f[i]=read();
		g=read();
		while(g--){
			ll z=read(),x=read(),re=0;
			for(int i=z;i<=x;i++)
			for(int j=z;j<=i;j++){
				ll m=0,n=0;
				for(int k=j;k<=i;k++)m=max(m,d[k]),n=max(n,f[k]);
				re+=m*n;
			}
			printf("%lld\n",re);
		}
	}
	return 0;
}
/*
0 2
2 1
1 2
1
1 2
*/