#include<bits/stdc++.h>
using namespace std;
int T, Q;
long long n;
long long a[250010], b[250010];
struct noip
{
	long long val, ip;
}st_a[20][250010], st_b[20][250010];
struct node
{
	long long l, r;
}a_max[250010], b_max[250010];
inline void build()
{
	for (long long i = 1; i <= 19; i++)
		for (long long j = 1; j + (1 << (i - 1)) <= n + 1; j++)
		{
			if (st_a[i - 1][j].val > st_a[i - 1][j + (1 << (i - 1))].val) st_a[i][j] = st_a[i - 1][j];
			else st_a[i][j] = st_a[i - 1][j + (1 << (i - 1))];
			a_max[st_a[i][j].ip].l = min(a_max[st_a[i][j].ip].l, j);
			a_max[st_a[i][j].ip].r = max(a_max[st_a[i][j].ip].r, min(j + (1 << i) - 1, n));
			if (st_b[i - 1][j].val > st_b[i - 1][j + (1 << (i - 1))].val) st_b[i][j] = st_b[i - 1][j];
			else st_b[i][j] = st_b[i - 1][j + (1 << (i - 1))];
			b_max[st_b[i][j].ip].l = min(b_max[st_b[i][j].ip].l, j);
			b_max[st_b[i][j].ip].r = max(b_max[st_b[i][j].ip].r, min(j + (1 << i) - 1, n));
		}
}
inline long long query_a(long long l, long long r)
{
	long long bp = log2(r - l + 1);
	return (st_a[bp][l].val > st_a[bp][r - (1 << bp) + 1].val ? st_a[bp][l].ip : st_a[bp][r - (1 << bp) + 1].ip);
}
inline long long query_b(long long l, long long r)
{
	long long bp = log2(r - l + 1);
	return (st_b[bp][l].val > st_b[bp][r - (1 << bp) + 1].val ? st_b[bp][l].ip : st_b[bp][r - (1 << bp) + 1].ip);
}
long long ans;
int main()
{
	freopen("match.in", "r", stdin);
	freopen("match.out", "w", stdout);
	cin >> T >> n;
	for (register int i = 1; i <= n; i++)
	{
		scanf("%lld", &a[i]);
		st_a[0][i].val = a[i], st_a[0][i].ip = i;
		a_max[i].l = a_max[i].r = i;
	}
	for (register int i = 1; i <= n; i++)
	{
		scanf("%lld", &b[i]);
		st_b[0][i].val = b[i], st_b[0][i].ip = i;
		b_max[i].l = b_max[i].r = i;
	}
	build();
	for (int i = 1; i <= n; i++)
		for (long long j = 1; j <= i; j++)
			if (i == query_a(j, a_max[i].r)) {a_max[i].l = j; break;}
	for (int i = 1; i <= n; i++)
		for (long long j = n; j >= i; j--)
			if (i == query_a(a_max[i].l, j)) {a_max[i].r = j; break;}
	cin >> Q;
	while (Q--)
	{
		long long L, R;
		scanf("%lld%lld", &L, &R);
		ans = 0;
		for (long long i = L; i <= R; i++)
		{
			long long pa = max(a_max[i].l, L), qa = min(a_max[i].r, R);
			while (1)
			{
				long long x = query_b(pa, qa);
				long long len = (min(x, i) - pa + 1) * (qa - max(i, x) + 1);
				ans += (long long)(a[i] * b[x] * len);
				if (i > x) pa = x + 1;
				else if (i < x) qa = x - 1;
				else if (i == x) break;
			}
		}
		printf("%llu\n", ans);
	}
	return 0;
}