#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define mkp make_pair
#define fi first
#define se second
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
const int N = 3010;
int T, n;
int mxa[N][N], mxb[N][N];
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", &mxa[i][i]);
	for(int i = 1; i <= n; i++)
		scanf("%d", &mxb[i][i]);
	for(int i = 1; i <= n; i++)
		for(int j = i + 1; j <= n; j++) {
			mxa[i][j] = max(mxa[i][j - 1], mxa[j][j]);
			mxb[i][j] = max(mxb[i][j - 1], mxb[j][j]);
		}
	int Q; scanf("%d", &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 = ans + (ull)mxa[p][q] * (ull)mxb[p][q];
		printf("%llu\n", ans);
	}
	return 0;
}
//感觉很莫队。。
