#include <bits/stdc++.h>
using namespace std;
const int N = 3002;
int n, m, p, t, ans, sum, cnt, tot, a[N], b[N], c[N], d[N], Q;
inline int rd()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}
void sub1()
{
	while (Q--)
	{
		ans = 0;
		int l = rd(), r = rd();
		for (int i = l; i <= r; i++)
		{
			for (int j = i; j <= r; j++)
			{
				p = 0, t = 0;
				for (int k = i; k <= j; k++) p = max(p, a[k]);
				for (int k = i; k <= j; k++) t = max(t, b[k]);
				ans += (p * t);
			}
		}
		cout << ans << endl;
	}
}
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int T = rd(); n = rd();
	for (int i = 1; i <= n; i++) a[i] = rd();
	for (int i = 1; i <= n; i++) b[i] = rd();
	Q = rd();
	if(T == 1 || T == 2 || T == 3 || T == 4 || T == 5) { sub1(); return 0; }
	else
	{
		while (Q--)
		{
			puts("1");
		}
	}
	return 0;
}

