#include<bits/stdc++.h>
#define int long long 
#define For(i,a,b) for ( int i=(a);i<=(b);i++ )
#define Dow(i,a,b) for ( int i=(a);i>=(b);i-- )
using namespace std;
const int N=35;
int T,n,m,Q,a[N],b[N],ma[N][N],mb[N][N];
signed main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	scanf("%lld%lld",&T,&n);	
	For(i,1,n) scanf("%lld",&a[i]),ma[i][i]=a[i];
	For(i,1,n) scanf("%lld",&b[i]),mb[i][i]=b[i];
	For(i,1,n) For(j,i+1,n) ma[i][j]=max(a[j],ma[i][j-1]);
	For(i,1,n) For(j,i+1,n) mb[i][j]=max(b[j],mb[i][j-1]);
	scanf("%lld",&Q);
	for (;Q--;)
	{
		int l,r,na,nb,ans;
		ans=0;
		scanf("%lld%lld",&l,&r);
		For(i,l,r) 
		For(j,i,r) ans+=ma[i][j]*mb[i][j];
		printf("%lld\n",ans);
	}
	return 0;
}
