#include <bits/stdc++.h>
#define int unsigned long long
#define OK
using namespace std;
int read ()
{
    char ch=getchar();
    int flag=1,x=0;
    while (ch<'0' || ch>'9')
    {
    	if (ch=='-') flag=-flag;
    	ch=getchar();
	}
	while (ch>='0' && ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return flag*x;
}
struct node
{
	int a,loc;
	node (int a=0,int loc=0): a(a),loc(loc) {}
};
inline bool operator< (node a,node b)
{
	return a.a<b.a;
}
struct segment_tree
{
	node a[1000005];
	void build (int i,int l,int r,int* s)
	{
		if (l>r) return;
		if (l==r) { a[i]=node(s[l],l); return; }
		int mid=(l+r)>>1;
		build (i<<1,l,mid,s);
		build (i<<1|1,mid+1,r,s);
		a[i]=max(a[i<<1],a[i<<1|1]);
	}
	node query (int i,int l,int r,int x,int y)
	{
//		printf ("%d %d %d %d %d %d\n",i,l,r,x,y,a[i]);
		if (y<l || x>r) return 0;
		if (x<=l && y>=r) return a[i];
		int mid=(l+r)>>1;
		return max (query(i<<1,l,mid,x,y),query(i<<1|1,mid+1,r,x,y));
	}
} ta,tb;
int T,n,Q,ans,a[250005],b[250005];
int f (int l,int r)
{
	if (l>r) return 0;
	if (l==r) return a[l]*b[l];
	node x=ta.query(1,1,n,l,r);
	int ans=f(l,x.loc-1)+f(x.loc+1,r),tmp=b[x.loc];
//	for (int p=l;p<=x.loc;p++)
//		for (int q=x.loc;q<=r;q++)
//		{
////			printf ("%d,%d=%d\n",p,x.loc,tb.query(1,1,n,p,x.loc).a);
////			printf ("%d,%d=%d\n",x.loc,q,tb.query(1,1,n,x.loc,q).a);
//			tmp+=max(tb.query(1,1,n,p,x.loc),tb.query(1,1,n,x.loc+1,q)).a;
//		}
	int p=x.loc,q=x.loc,v=b[p],w=b[p];
	while (p>l && q<r)
	{
		while (1)
		{
			p--;
			if (b[p]>v) v=b[p];
			tmp+=max(v,w)*(q-x.loc+1);
//			printf ("p=%d q=%d v=%d w=%d tmp+=%d\n",p,q,v,w,max(v,w)*(q-x.loc+1));
			if (p==l) break;
			if (v>w) break;
		}
		if (p==l) break;
		while (1)
		{
			q++;
			if (b[q]>w) w=b[q];
			tmp+=max(v,w)*(x.loc-p+1);
//			printf ("p=%d q=%d v=%d w=%d tmp+=%d\n",p,q,v,w,max(v,w)*(x.loc-p+1));
			if (q==r) break;
			if (w>v) break;
		}
		if (q==r) break;
	}
	while (p>l)
	{
		p--;
		if (b[p]>v) v=b[p];
		tmp+=max(v,w)*(q-x.loc+1);
//			printf ("p=%d q=%d v=%d w=%d tmp+=%d\n",p,q,v,w,max(v,w)*(q-x.loc+1));
	}
	while (q<r)
	{
		q++;
		if (b[q]>w) w=b[q];
		tmp+=max(v,w)*(x.loc-p+1);
//			printf ("p=%d q=%d v=%d w=%d tmp+=%d\n",p,q,v,w,max(v,w)*(x.loc-p+1));
	}
//	printf ("%d,%d ans=%d tmp=%d %d\n",l,r,ans,tmp,ans+x.a*tmp);
	return ans+x.a*tmp;
}
signed main ()
{
#ifdef OK
	freopen ("match.in","r",stdin);
	freopen ("match.out","w",stdout);
#endif
	T=read(); n=read();
	for (int i=1;i<=n;i++) a[i]=read();
	for (int i=1;i<=n;i++) b[i]=read();
	ta.build(1,1,n,a);
	tb.build(1,1,n,b);
	Q=read();
	while (Q--)
	{
		int l=read(),r=read();
		ans=0;
		if (n<=3000)
		{
			for (int p=l;p<=r;p++)
				for (int q=p;q<=r;q++)
				{
					int x=ta.query(1,1,n,p,q).a;
					int y=tb.query(1,1,n,p,q).a;
					ans+=x*y;
	//				printf ("(%d,%d):%d*%d=%d\n",p,q,x,y,x*y);
				}
			printf ("%llu\n",ans);
		}
		else printf ("%llu\n",f(l,r));
	}
#ifndef OK
	printf ("%d\n",clock());
#endif
	return 0;
}
// 最后 10 分钟，死活调不出来，发现做法假了，时间复杂度也假了 T_T 
// 还好打了暴力 
