#include<cstdio>
#include<iostream>
#define MAXN 3005
#define ull unsigned long long
using namespace std;
int l,r,Q,T,n,a[MAXN],b[MAXN],maxa[MAXN][MAXN],maxb[MAXN][MAXN];
int main() {
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	scanf("%d%d", &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++) {
		maxa[i][i]=a[i];
		maxb[i][i]=b[i];
		for (int j=i+1; j<=n; j++) {
			maxa[i][j]=max(maxa[i][j-1],a[j]);
			maxb[i][j]=max(maxb[i][j-1],b[j]);
		}
	}
	scanf("%d", &Q);
	while (Q--) {
		ull ans=0;
		scanf("%d%d", &l, &r);
		for (int i=l; i<=r; i++) {
			for (int j=i; j<=r; j++) {
				ans+=maxa[i][j]*maxb[i][j];
			}
		}
		printf("%u", ans);
 	}
	return 0;
}