#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
	int x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();}
	while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
	return x * f;
}
const int N = 3050, M = 3e5 + 10;
int T, n, Q;
int ans[N][N], a[M][2], g[N][N], f[M];
signed main () {
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	T = read(), n = read();
	for (int i = 1; i <= n; ++ i) a[i][0] = read();
	for (int i = 1; i <= n; ++ i) a[i][1] = read();
	if (n <= 3000) {
		for (int i = 1; i <= n; ++ i) {
			g[i][i] = a[i][0] * a[i][1]; int maxa = a[i][0], maxb = a[i][1];
			for (int j = i + 1; j <= n; ++ j) {
				maxa = max(maxa, a[j][0]); maxb = max(maxb, a[j][1]);
				g[i][j] = g[i][j-1] + maxa * maxb; 
			}
		}
		for (int i = 1; i <= n; ++ i) ans[i][i] = a[i][0] * a[i][1];
		for (int len = 2; len <= n; ++ len)
			for (int i = 1; i <= n; ++ i) {
				int j = i + len - 1; if (j > n) break;
				ans[i][j] = ans[i+1][j] + g[i][j];
			}
		int Q = read();
		while (Q --) {
			int l = read(), r = read();
			printf("%lld\n", ans[l][r]);
		} 
	} else {
		int Q = read();
		while (Q --) {
			int l = read(), r = read();
			memset(f, 0, sizeof f);
			f[l] = a[l][0] * a[l][1]; int maxa = a[l][0], maxb = a[l][1];
			for (int i = l+1; i <= r; ++ i) {
				maxa = max(maxa, a[i][0]); maxb = max(maxb, a[i][1]);
				f[i] = f[i-1] + maxa * maxb;
			}
			int res = 0;
			for (int i = l; i <= r; ++ i) res += f[i];
			printf("%lld\n", res);
		}
	}
	return 0;
}
