#include<bits/stdc++.h>
using namespace std;

#define Reimu inline void
#define Marisa inline int
#define Sanae inline bool
#define Reisen inline LL

typedef long long LL;
typedef unsigned long long ULL;

typedef pair<int, int> Pii;
typedef tuple<int, int, int> Tiii;
#define fi first
#define se second

const int N = 3010;

int n;
unsigned a[N], b[N];
ULL s[N][N];

struct ST {
	unsigned st[20][N];
	Reimu init(unsigned *a, int n) {
		memcpy(st[0] + 1, a + 1, n << 2);
		for (int i = 1; 1 << i <= n; ++i) {
			for (int j = 1; j <= n - (1 << i) + 1; ++j) {
				st[i][j] = max(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
			}
		}
	}
	Marisa operator()(int l, int r) {
		int k = __lg(r - l + 1);
		return max(st[k][l], st[k][r - (1 << k) + 1]);
	}
} st1, st2;

int main() {
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int O; cin >> O >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= n; ++i) cin >> b[i];
	st1.init(a, n); st2.init(b, n);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= i; ++j) {
			s[i][j] = s[i][j - 1] + 1ULL * st1(j, i) * st2(j, i);
		}
	}
	int q; cin >> q; while (q--) {
		int l, r; cin >> l >> r;
		ULL ans = 0;
		for (int i = l; i <= r; ++i) ans += s[i][i] - s[i][l - 1];
		cout << ans << '\n';
	}
	return 0;
}

