#include<algorithm>
#include<cstdio>
const int N = 250010,S = 498,_N = 3010;///////////////////////////////
typedef unsigned long long ull;
char ch;
void read(int &x)
{
	x = 0,ch = getchar();
	while (ch < '0' || ch > '9')
		ch = getchar();
	while (ch >= '0' && ch <= '9')
		x = x*10+ch-48,ch = getchar();
}

/*int T,n,a[N],sta[N],topa,stb[N],topb,posa[N],posb[N],Q,b[N];
ull ans[N],suma,sumb,ansa,ansb;
struct Query{
	int l,r,xh;
}q[N];

struct Tree{
	int ls[N],rs[N],prev[N],next[N],root;
	
	void Build(const int *a,const int &n)
	{
		st[top = 1] = root = a[1],prev[a[1]] = -1;
		for (int i = 2;i <= n;++i)
		{
			while (top && st[top] < a[i])
				next[st[top]] = a[i],ls[a[i]] = st[top--];
			if (top)
				rs[st[top]] = a[i],prev[a[i]] = st[top];
			else
				root = a[i],prev[a[i]] = -1;
			st[++top] = a[i];
		}
		while (top)
			next[st[top--]] = n+1;
	}
	
	void print(int n)
	{
		printf("root=%d\n",root);
		for (int i = 1;i <= n;++i)
			printf("  #%d ls->%d rs->%d prev=%d next=%d\n",i,ls[i],rs[i],prev[i],next[i]);
	}
}ta,tb,tc,td;

bool cmp(Query x,Query y)
{
	return x.l/S < y.l/S || (x.l/S == y.l/S && x.r < y.r);
}*/
int T,n,a[N],b[N],l,r,maxa,maxb,Q;
ull sum[_N][_N],ans;

int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	read(T),read(n);
	for (int i = 1;i <= n;++i)
		read(a[i]);
	for (int i = 1;i <= n;++i)
		read(b[i]);
	for (int i = 1;i <= n;++i)
	{
		maxa = a[i],maxb = b[i],sum[i][i] = a[i]*b[i];
		for (int j = i+1;j <= n;++j)
			maxa = std::max(maxa,a[j]),maxb = std::max(maxb,b[j]),
			sum[i][j] = sum[i][j-1]+maxa*maxb;
	}
	read(Q);
	for (int i = 1;i <= Q;++i)
	{
		read(l),read(r),ans = 0;
		for (int j = l;j <= r;++j)
			ans += sum[j][r]-sum[j][l-1];
		printf("%llu\n",ans);
	}
/*	for (int i = 1;i <= n;++i)
		read(a[i]),posa[a[i]] = i;
	for (int i = 1;i <= n;++i)
		read(b[i]),posb[b[i]] = i;
	read(Q);
	for (int i = 1;i <= Q;++i)
		read(q[i].l),read(q[i].r),q[i].xh = i;
	std::sort(q+1,q+Q+1,cmp);
	for (int i = 1;i <= Q;++i)
	{
	//	if (q[i].r < (q[i].l/S+1)*S)
		{
			posa[0] = posb[0] = q[i].l-1;
			ansa = suma = sta[topa = 1] = a[q[i].l],ansb = sumb = stb[topb = 1] = b[q[i].l],++q[i].l;
			while (q[i].l <= q[i].r)
			{
				while (topa && sta[topa] <= a[q[i].l])
					suma -= sta[topa]*(posa[sta[topa]]-posa[sta[topa-1]]),--topa;
				while (topb && stb[topb] <= b[q[i].l])
					sumb -= stb[topb]*(posb[stb[topb]]-posb[stb[topb-1]]),--topb;
				suma += a[q[i].l]*(q[i].l-posa[sta[topa]]);
				sumb += b[q[i].l]*(q[i].l-posb[stb[topb]]);
				sta[++topa] = a[q[i].l],stb[++topb] = b[q[i].l];
				ansa += suma,ansb += sumb,++q[i].l;
			}
			ans[q[i].xh] = ansa*ansb;
		}
	}
	for (int i = 1;i <= Q;++i)
		printf("%llu\n",ans[i]);*/
	return 0;
}