#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e3 + 10;
int T, n, Q;
int a[MAXN], b[MAXN];
int mx1[MAXN][MAXN], mx2[MAXN][MAXN];
int tree[2][MAXN << 2];
#define lson (node << 1)
#define rson (node << 1 | 1)
void push_up(int node, int id)
{
	tree[id][node] = max(tree[id][lson], tree[id][rson]);
}
void build (int node, int l, int r, int id)
{
	if (l == r)
	{
		if (id == 0)
			tree[id][node] = a[l];
		else
			tree[id][node] = b[l];
		return;
	}
	int mid = l + r >> 1;
	build (lson, l, mid, id);
	build (rson, mid + 1, r, id);
	push_up(node, id);
}
int ask(int node, int l, int r, int L, int R, int id)
{
	if (L <= l && r <= R)
		return tree[id][node];
	int ans = 0;
	int mid = l + r >> 1;
	if (L <= mid)
		ans = max(ans, ask(lson, l, mid, L, R, id));
	if (R > mid)
		ans = max(ans, ask(rson, mid + 1, r, L, R, id));
	return ans;
}
signed main()
{
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	cin >> T >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
		cin >> b[i];
	build(1, 1, n, 0);
	build(1, 1, n, 1);
	for (int i = 1; i <= n; i++)
	{
		for (int j = i; j <= n; j++)
		{
			mx1[i][j] = ask(1, 1, n, i, j, 0);
			mx2[i][j] = ask(1, 1, n, i, j, 1);
		}
	}
//	cout << ask(1, 1, n, 1, 2, 0) << endl;
	cin >> Q;
	while(Q--)
	{
		int l, r;
		cin >> l >> r;
		unsigned long long ans = 0;
		for (int i = l; i <= r; i++)
			for (int j = i; j <= r; j++)
				ans = (ans + mx1[i][j] * mx2[i][j]);
		cout << ans << endl;
	}
	return 0;
}
