#include <bits/stdc++.h>

using namespace std;

int read() {
	int x=0, f=0; char c=getchar();
	while (!isdigit(c)) f|=c=='-', c=getchar();
	while (isdigit(c)) x=(x<<3)+(x<<1)+(c^48), c=getchar();
	return f ? -x : x;
}

const int N=3e3+10;
int n, q;
unsigned long long a[N], b[N], g[N][N], f[N][N], sum;

int main() {
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	int T=read(); n=read();
	for (int i=1; i<=n; i++) a[i]=read();
	for (int i=1; i<=n; i++) b[i]=read();
	for (int i=1; i<=n; i++) {
		unsigned long long mx1=0, mx2=0;
		for (int j=i; j>=1; j--) {
			mx1=max(mx1, a[j]);
			mx2=max(mx2, b[j]);
			g[j][i]=g[j+1][i]+mx1*mx2;
		}
	}
	for (int i=1; i<=n; i++) {
		for (int j=i; j<=n; j++) {
			f[i][j]=f[i][j-1]+g[i][j];
		}
	}
	q=read();
	while (q--) {
		int l=read(), r=read();
		cout<<f[l][r]<<endl;
	}
	return 0;
}