#include<bits/stdc++.h>
#define fo(x,l,r) for (int x=(l); x<=(r); x++)
#define dw(x,r,l) for (int x=(r); x>=(l); x--)
#define int unsigned long long
using namespace std;
const int N=3006;
int T,n,Q,a[N],b[N],ma[N][N],mb[N][N],x[N][N];
int ans[N][N];
signed main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>T>>n;
	fo(i,1,n) cin>>a[i];
	fo(i,1,n) cin>>b[i];
	fo(i,1,n) fo(j,i,n)
	ma[i][j]=max(ma[i][j-1],a[j]);
	fo(i,1,n) fo(j,i,n)
	mb[i][j]=max(mb[i][j-1],b[j]);
	fo(i,1,n) fo(j,i,n) x[i][j]=x[i-1][j]+ma[i][j]*mb[i][j];
	fo(i,1,n) fo(j,i,n) ans[i][j]=ans[i][j-1]+x[j][j]-x[i-1][j];
	cin>>Q;
	while (Q--){
		int l,r; cin>>l>>r;
		cout<<ans[l][r]<<endl;
	}
	return 0;
}