#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define For(i,l,r) for(ll i=l,i##end=r;i<=i##end;++i)
#define Rep(i,l,r) for(ll i=l,i##end=r;i<i##end;++i)
#define FOR(i,l,r) for(ll i=l,i##end=r;i>=i##end;--i)
ll read(){
	ll v=0;bool f=1;char c=getchar();
	for(;'0'>c||c>'9';c=getchar())
	    if(c=='-') f = 0;
	for(;'0'<=c&&c<='9';c=getchar())
	    v = (v<<3)+(v<<1)+(c^48);
	return f?v:-v;
}
const ll N = 25e4+10;
ll T,n,Q;
ll a[N],b[N];
namespace List{
ll lasa[N],nexa[N],lasb[N],nexb[N],xa[N],xb[N];
void work(){
	For(i,1,n) xa[a[i]] = i,xb[b[i]] = i;
	//first one bigger
	For(i,0,n+1) lasa[i] = i-1,nexa[i] = i+1;
	For(i,0,n+1) lasb[i] = i-1,nexb[i] = i+1;
	For(i,1,n){
		lasa[nexa[xa[i]]] = lasa[xa[i]];
		nexa[lasa[xa[i]]] = nexa[xa[i]];
		lasb[nexb[xb[i]]] = lasb[xb[i]];
		nexb[lasb[xb[i]]] = nexb[xb[i]];
	}
//	For(i,1,n) printf("%lld %lld\n",lasa[i],nexa[i]);
}
}
namespace A{
unsigned ll num[3010][3010],lum[3010][3010];
void work(){
	For(i,1,n){
		ll maxa = a[i],maxb = b[i];
		num[i][i] = maxa*maxb;
	    For(j,i+1,n){
	    	maxa = max(maxa,a[j]);
	    	maxb = max(maxb,b[j]);
	    	num[i][j] = maxa*maxb;
		}
	}
	//lum[i][r] = For(j,i,r) +num[i][j]
	For(i,1,n) For(r,i,n) lum[i][r] = lum[i][r-1]+num[i][r];
	For(qwq,1,Q){
		ll l=read(),r=read();
		unsigned ll sum = 0;
		For(i,l,r) sum += lum[i][r];
//		For(i,l,r) For(j,i,r) sum += num[i][j];
		printf("%llu\n",sum);
	}
}
}
//namespace B{
//void work(){
//	bk = srqt(n);
//	for(ll l=1,r=bl;l<=n;l=r+1,r=min(n,r+bk)){
//		++cnt;bl[cnt] = l,br[cnt] = r;
//		For(i,l,r) bel[i] = cnt;
//		For(i,l,r) mxa[cnt] = max(mxa[cnt],a[i]);
//		For(i,l,r) mxb[cnt] = max(mxb[cnt],b[i]);
//	}
//	For(i,1,cnt){
//		For(l,bl[i],br[i]){
//			ll maxa = 0,maxb = 0;
//			For(r,l,br[i]){
//				maxa = max(maxa,a[r]);
//				maxb = max(maxb,b[r]);
//				sum[i] += maxa*maxb;
//			}
//		}
//	}
//	For(i,1,cnt){
//	    ll maxa = mxa[i],maxb = mxb[i];
//		For(j,i+1,cnt){
//			lum[i][j] = 
//		}
//		
//	}
//}
//}

int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	
	T=read(),n=read();
	For(i,1,n) a[i]=read();
	For(i,1,n) b[i]=read();
	Q=read();
	A::work();
	
	fclose(stdin);fclose(stdout);
	return 0;
}
