#include <bits/stdc++.h>

int main()
{
#ifndef CM_DEBUG
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
#endif

	const int N = 3005;

	int n;
	scanf("%*d%d", &n);

	static uint64_t a[N], b[N];
	for (int i = 1; i <= n; i++)
		scanf("%" SCNu64, &a[i]);
	for (int i = 1; i <= n; i++)
		scanf("%" SCNu64, &b[i]);

	static uint64_t best[N][N];
	for (int i = 1; i <= n; i++)
	{
		uint64_t a_max = 0, b_max = 0;
		for (int j = i; j <= n; j++)
		{
			a_max = std::max(a_max, a[j]);
			b_max = std::max(b_max, b[j]);
			best[i][j] = a_max * b_max;
		}
	}

	for (int i = n - 1; i >= 1; i--)
		for (int j = i + 1; j <= n; j++)
			best[i][j] = best[i][j] + best[i + 1][j] + best[i][j - 1] - best[i + 1][j - 1];

	int q;
	scanf("%d", &q);
	for (int i = 0; i < q; i++)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		printf("%" SCNu64 "\n", best[l][r]);
	}

	return 0;
}
