#include <bits/stdc++.h>
using namespace std;
const int N=250000;
#define ull unsigned long long

int n;
ull gp[3010][3010],a[N+9],b[N+9];

int main() {
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int id___;
	scanf("%d%d",&id___,&n);
	for (int i=1;i<=n;i++) scanf("%u",a+i);
	for (int i=1;i<=n;i++) scanf("%u",b+i);
	if (n<=3000) {
		for (int l=1;l<=n;l++) {
			ull ma=a[l],mb=b[l];
			for (int r=l;r<=n;r++) {
				ma=max(ma,a[r]),mb=max(mb,b[r]);
				gp[l][r]=ma*mb;
			}
		}
		for (int r=n;r>=1;r--)
			for (int l=r-1;l>=1;l--)
				gp[l][r]+=gp[l+1][r];
		for (int l=1;l<=n;l++)
			for (int r=l;r<=n;r++)
				gp[l][r]+=gp[l][r-1];
		int T;
		scanf("%d",&T);
		while (T--) {
			int l,r;
			scanf("%d%d",&l,&r);
			printf("%u\n",gp[l][r]);
		}
	}
	return 0;
}
