#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int maxn = 3010;
int n, q;
ll a[maxn], b[maxn], ma[maxn][maxn], mb[maxn][maxn], pro[maxn];
int main()	{
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	int t;
	scanf("%d%d", &t, &n);
	for (int i = 1; i <= n; i++)
		scanf("%llu", &a[i]);
	for (int i = 1; i <= n; i++)
		scanf("%llu", &b[i]);
	for (int len = 1; len <= n; len++)	
		for (int i = 1; i + len - 1 <= n; i++)	{
			int r = len + i - 1;
			ma[i][r] = max(a[r], ma[i][r - 1]);
			mb[i][r] = max(b[r], mb[i][r - 1]);
		}
	scanf("%d", &q);
	while (q--)	{
		int l, r;
		scanf("%d%d", &l, &r);
		ll ans = 0;
		for(int i = l; i <= r; i++)
			for(int j = i; j <= r; j++)
				ans += ma[i][j] * mb[i][j];
		printf("%llu\n", ans);
	}
	return 0;
}