//I love Seele forever!
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
int n,m;
struct sub
{
	int a[300010];
	int f[300010][21],L[300010],R[300010];
	ull t[300010];
	int query(int l,int r)
	{
		int len=__lg(r-l+1);
		return cmp(f[l][len],f[r-(1<<len)+1][len]);
	}
	int cmp(int x,int y)
	{
		return a[x]<a[y]?y:x;
	}
	int ls[800010],rs[800010],rt,cnt;
	void build(int &x,int l,int r)
	{
		x=++cnt;
		int mid=query(l,r);
		t[x]=1ull*a[mid]*(mid-l+1)*(r-mid+1);
		L[mid]=l,R[mid]=r;
		if(l!=mid)
			build(ls[x],l,mid-1),t[x]+=t[ls[x]];
		if(r!=mid)
			build(rs[x],mid+1,r),t[x]+=t[rs[x]];
	}
	ull solve(int x,int l,int r,int ll,int rr)
	{
		if(ll>rr)
			return 0;
		if(x==0)
			return 0;
		if(ll<=l&&r<=rr)
			return t[x];
		if(r<ll||rr<l)
			return 0;
		int mid=query(l,r);
		ull res=(ll<=mid&&mid<=rr?1ull*a[mid]*(mid-max(ll,l)+1ull)*(min(rr,r)-mid+1ull):0);
		return solve(ls[x],l,mid-1,ll,rr)+solve(rs[x],mid+1,r,ll,rr)+res;
	}
	void init()
	{
		for(int i=1;i<=n;i++)
			scanf("%d",&a[i]),f[i][0]=i;
		for(int j=1;j<=20;j++)
			for(int i=1;i<=n;i++)
				if(i+(1<<j)-1<=n)
					f[i][j]=cmp(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		build(rt,1,n);
	}
};
sub a,b;
int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int id;
	scanf("%d%d",&id,&n);
	a.init();
	b.init();
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		ull ans=0;
		for(int j=l;j<=r;j++)
			ans+=1ull*a.a[j]*(b.solve(1,1,n,max(a.L[j],l),min(a.R[j],r))-b.solve(1,1,n,max(a.L[j],l),j-1)-b.solve(1,1,n,j+1,min(a.R[j],r)));
		printf("%llu\n",ans);
	}
}
//Beaten by sunzh
