#include <bits/stdc++.h>
#define forn(i,s,t) for(int i=(s); i<=(t); ++i)
#define form(i,s,t) for(int i=(s); i>=(t); --i)
#define rep(i,s,t) for(int i=(s); i<(t); ++i)
typedef long long i64;
typedef unsigned long long u64;
using namespace std;
const int N = 2.5e5 + 3;

int Trd, n, Q, a[N], b[N];
namespace SUB1 {
	const int M = 3e3 + 3;
	u64 f[M][M], ans[M][M];
	inline void solve() {
		forn (r, 1, n) {
			int Mxa = 0, Mxb = 0;
			form (l, r, 1) {
				Mxa = max(Mxa, a[l]);
				Mxb = max(Mxb, b[l]);
				f[l][r] = f[l + 1][r] + 1ull * Mxa * Mxb;
			}
		}
//		forn (l, 1, n) forn (r, 1, n) cout << f[l][r] << " \n"[r == n];
		forn (l, 1, n) forn (r, l, n) ans[l][r] = ans[l][r - 1] + f[l][r];
		while (Q--) {
			int l, r;
			cin >> l >> r;
			cout << ans[l][r] << '\n';
		}
	}
}
int main() {
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> Trd >> n;
	forn (i, 1, n) cin >> a[i];
	forn (i, 1, n) cin >> b[i];
	cin >> Q;
	if (n <= 3000) SUB1 :: solve();
	return 0;
}