#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)

const long long N=3005;

long long n,m,T,Q;
long long a[N],b[N];
long long fty1[N][N];
long long fty2[N][N];
long long ans[N][N];
long long sum[N][N];


void work1(){
	FOR(i,1,n) cin>>a[i];
	FOR(i,1,n) cin>>b[i];
	cin>>Q;
	FOR(l,1,n){
		long long Max1=0,Max2=0;
		FOR(r,l,n){
			Max1=max(Max1,a[r]);
			Max2=max(Max2,b[r]);
			fty1[l][r]=Max1;
			fty2[l][r]=Max2;
		}
	}
	FOR(l,1,n){
		FOR(r,l,n){
			ans[l][r]=fty1[l][r]*fty2[l][r];
			sum[l][r]=ans[l][r]+sum[l][r-1];
		}
	}
	while(Q--){
		long long l,r;
		cin>>l>>r;
		long long Ans=0;
		
//		FOR(i,l,r){
//			FOR(j,i,r) Ans+=ans[i][j];
//		}
		
		FOR(i,l,r){
			Ans+=sum[i][r]-sum[i][i-1];
		}

		cout<<Ans;
		puts("");
	}
}

int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);

	cin>>T>>n;
	if(T<=5){
		memset(fty1,0,sizeof fty1);
		memset(fty2,0,sizeof fty2);
		memset(ans,0,sizeof ans);
		memset(sum,0,sizeof sum);
		work1();
		return 0;
	}
	return 0;
}