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

const int maxn = 10005;

int T;
int n;
int q;
ll a[maxn];
ll b[maxn];
ll maxa[maxn][maxn];
ll maxb[maxn][maxn];
ll ans;

int main()
{
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	cin >> T;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> b[i];
	}
	for (int i = 1; i <= n; i++)
	{
		int l, r;
		l = r = i;
		while (l >= 0 && a[l] <= a[i]) l--;
		while (r <= n && a[r] <= a[i]) r++;
		for (int j = l + 1; j <= i; j++)
		{
			for (int k = i; k < r; k++)
			{
				maxa[j][k] = a[i];
			}
		}
	}
	for (int i = 1; i <= n; i++)
	{
		int l, r;
		l = r = i;
		while (l >= 0 && b[l] <= b[i]) l--;
		while (r <= n && b[r] <= b[i]) r++;
		for (int j = l + 1; j <= i; j++)
		{
			for (int k = i; k < r; k++)
			{
				maxb[j][k] = b[i];
			}
		}
	}
	cin >> q;
	while (q--)
	{
		ans = 0;
		int l, r;
		cin >> l >> r;
		for (int i = l; i <= r; i++)
		{
			for (int j = l; j <= r; j++)
			{
				ans += maxa[i][j] * maxb[i][j];
			}
		}
		cout << ans << endl;
	}
	return 0;
}
