#include<bits/stdc++.h>
using namespace std;
int T,n,q,x,l1,l2,r1,r2,sum;
long long ans,ansb,ansa,f1[2500000],f2[2500000],l[2500000],r[2500000];
long long max(long long a,long long b)
{
   if (a>b) return a;
   else return b;
}
long long min(long long a,long long b )
{
  if (a<b) return a;
  else return b;
}
void build(int t,int x,int y,long long f[2500000]) {
	l[t]=x;
	r[t]=y;
	if (x==y) {
		int w;
		cin>>w;
		f[t]=w;
		return;
	}
	int mid;
	mid=(x+y)/2;
	build(t*2,x,mid,f);
	build(t*2+1,mid+1,y,f);
	f[t]=max(f[t*2],f[t*2+1]);
}
void asum(int t)
{
	if (l2<=l[t]&&r2>=r[t])
	{
		ansa=max(ansa,f1[t]);
		return;
	}
	int mid;
	mid=(l[t]+r[t])/2;
	if (l2<=mid) asum(t*2);
	if  (r2>mid) asum(t*2+1);
}
void bsum(int t)
{
	if (l2<=l[t]&&r2>=r[t])
	{
		ansb=max(ansb,f2[t]);
		return;
	}
	int mid;
	mid=(l[t]+r[t])/2;
	if (l2<=mid) bsum(t*2);
	if  (r2>mid) bsum(t*2+1);
}
int main() {
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
    cin>>T>>n;
    build(1,1,n,f1);
    build(1,1,n,f2);
    cin>>q;
    for (int i=1;i<=q;i++)
    {
    	sum=0;
    	cin>>l1>>r1;
    	for (l2=l1;l2<=r1;l2++)
    	  for (r2=l2;r2<=r1;r2++)
    	    {
    	    	ansa=0;
    	    	ansb=0;
    	    	asum(1);
    	    	bsum(1);
    	    	sum=sum+ansa*ansb;
			}
		cout<<sum<<endl;
	}
	return 0;
}
