#include<bits/stdc++.h>
using namespace std;

template<class T>inline void read(T&x){
	char c,last=' ';
	while(!isdigit(c=getchar()))last=c;
	x=c^48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+(c^48);
	if(last=='-')x=-x;
}

#define ull unsigned long long
const int MAXN=2.5e5+7;
int n,q,siz;
ull a[MAXN],b[MAXN];
ull STa[MAXN][20],STb[MAXN][20],lg[MAXN];
struct node{
	int l,r,id;
}qry[MAXN];
ull ans[MAXN];
bool cmp(const node&a,const node&b){
	if((a.l-1)/siz+1!=(b.l-1)/siz+1)return (a.l-1)/siz+1<(b.l-1)/siz+1;
	if(((a.l-1)/siz+1)&1)return a.r<b.r;
	return a.r>b.r;
}

void init(){
	for(int i=2;i<=n;++i)lg[i]=lg[i>>1]+1;
	int k=lg[n];
	for(int i=1;i<=n;++i)STa[i][0]=a[i],STb[i][0]=b[i];
	for(int j=1;j<=k;++j){
		for(int i=1;i+(1<<j)-1<=n;++i){
			STa[i][j]=max(STa[i][j-1],STa[i+(1<<j-1)][j-1]);
			STb[i][j]=max(STb[i][j-1],STb[i+(1<<j-1)][j-1]);
		}
	}
}

int queryA(int l,int r){
	int k=lg[r-l+1];
	return max(STa[l][k],STa[r-(1<<k)+1][k]);
}
int queryB(int l,int r){
	int k=lg[r-l+1];
	return max(STb[l][k],STb[r-(1<<k)+1][k]);
}

namespace Brute{
	ull pre[3007][3007];
	void Init(){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				if(j<=i)pre[i][j]=queryA(j,i)*queryB(j,i);
				else pre[i][j]=queryA(i,j)*queryB(i,j);
			}
			for(int j=i-1;j>=1;--j)pre[i][j]+=pre[i][j+1];
			for(int j=i+1;j<=n;++j)pre[i][j]+=pre[i][j-1];
		}
	}
	void solve(){
		Init();
		sort(qry+1,qry+q+1,cmp);
		int l=1,r=0;
		ull res=0;
		for(int i=1;i<=q;++i){
			while(r<qry[i].r){++r;res+=pre[r][l];}
			while(l>qry[i].l){--l;res+=pre[l][r];}
			while(r>qry[i].r){res-=pre[r][l];--r;}
			while(l<qry[i].l){res-=pre[l][r];++l;}
			ans[qry[i].id]=res;
		}
		for(int i=1;i<=q;++i)cout<<ans[i]<<'\n';
	}
}

namespace Brute2{
	ull t[MAXN];
	void add(int x,ull d){
		for(;x<=n;x+=(x&-x))t[x]+=d;
	}
	ull sum(int x){
		ull ret=0;
		for(;x;x-=(x&-x))ret+=t[x];
		return ret;
	}
	void solve(){
		for(int T=1;T<=q;++T){
			int l=qry[T].l,r=qry[T].r;
			ull res=a[l]*b[l];
			memset(t,0,sizeof(t));
			add(l,a[l]*b[l]);
			for(int i=l+1;i<=r;++i){
				ull ma=a[i],mb=b[i];
				res+=ma*mb;
				add(i,ma*mb);
				for(int j=i-1;j>=l;--j){
					ma=max(ma,a[j]);
					mb=max(mb,b[j]);
					if(ma>a[i]&&mb>b[i]){
						res+=sum(j);
						break;
					}
					add(j,-sum(j)+sum(j-1));
					add(j,ma*mb);
					res+=ma*mb;
				}
			}
			cout<<res<<'\n';
		}
	}
}

int main()
{
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	int T;read(T);
	read(n);siz=(int)sqrt(n);
	for(int i=1;i<=n;++i)read(a[i]);
	for(int i=1;i<=n;++i)read(b[i]);
	read(q);
	for(int i=1;i<=q;++i){
		read(qry[i].l),read(qry[i].r);
		qry[i].id=i;
	}
	if(n<=3000){
		init();
		Brute::solve();
		exit(0);
	}
	if(q<=5){
		Brute2::solve();
		exit(0);
	}
	return 0;
}
