#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;
using ll = long long;
using ull = unsigned long long ;
using pii = pair<int, int>;
using vi = vector<int>;
using vii = vector<pii>;

const int N = 3005;

int n, Q;
int a[N], b[N];
int ls[N], rs[N];
int stk1[N], top1;
int stk2[N], top2;
int L1[N], R1[N];
int L2[N], R2[N];

int mxa[N][N], mxb[N][N];
ull ans[N][N];

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("%d", &a[i]);
	for (int i = 1; i <= n; i++) scanf("%d", &b[i]);
	for (int i = 1; i <= n; i++)
	{
		mxa[i][i] = a[i];
		mxb[i][i] = b[i];
		for (int j = i + 1; j <= n; j++)
			mxa[i][j] = max(mxa[i][j - 1], a[j]),
			mxb[i][j] = max(mxb[i][j - 1], b[j]);
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = i; j <= n; j++)
			ans[i][j] = (ans[i][j - 1] + 1ull * mxa[i][j] * mxb[i][j]);
	}
	scanf("%d", &Q);
	while (Q--)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		ull res = 0;
		for (int i = l; i <= r; i++)
			res += ans[i][r];
		printf("%llu\n", res);
	}
}
