#include<bits/stdc++.h>
using namespace std;
#define N 3003
#define ull unsigned long long
int T, Q, n, a[N], b[N];
int sta[N][23], stb[N][23];
int getmx(int l, int r, int p){
	int id = log2(r-l+1);
	if(p == 0) return max(sta[l][id], sta[r-(1<<id)+1][id]);
	else return max(stb[l][id], stb[r-(1<<id)+1][id]);
}
int main(){
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	cin>>T>>n;
	for(int i=1;i<=n;i++) scanf("%d", a+i);
	for(int i=1;i<=n;i++) scanf("%d", b+i);
	for(int i=1;i<=n;i++) sta[i][0] = a[i];
	for(int i=1;i<=n;i++) stb[i][0] = b[i];
	for(int j=1;1<<j<=n;j++){
		for(int i=1;i+(1<<j)-1 <= n;i++){
			sta[i][j] = max(sta[i][j-1], sta[i+(1<<j-1)][j-1]);
			stb[i][j] = max(stb[i][j-1], stb[i+(1<<j-1)][j-1]);
		}
	}
	cin>>Q;
	while(Q--){
		int l, r; scanf("%d%d", &l, &r);
		ull ans = 0;
		for(int p=l;p<=r;p++){
			for(int q=p;q<=r;q++){
				ans += (ull)getmx(p, q, 0) * getmx(p, q, 1);
			}
		}
		cout<<ans<<endl;
	}
}
