#include<bits/stdc++.h>
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define PF(i,a,b) for(int i=(a);i>=(b);--i)
#define Max(a,b) (((a)<(b)) and (a=b))
#define Min(a,b) (((a)>(b)) and (a=b))
#define ll long long
#define ull unsigned long long
using namespace std;
bool beginning;
namespace solve {
	bool beginning;
	inline int read();
	const int N=1e5+5;
	int T,n,a[N],b[N],Q;
	struct Query {
		int l,r,id;
		Query(int a=0,int b=0) {
			l=a,r=b;
		}
		bool operator <(const Query a)const {
			return l==a.l?r<a.r:l<a.l;
		}
	} q[N];
	namespace solve1 {
		inline ull solve(int l,int r) {
			ull s=0;
			F(i,l,r) {
				int Mx1=-1,Mx2=-1;
				F(j,i,r) {
					Max(Mx1,a[j]),Max(Mx2,b[j]);
					s+=1ull*Mx1*Mx2;
				}
			}
			return s;
		}
		void main() {
			F(i,1,Q) {
				ull Ans=solve(q[i].l,q[i].r);
				printf("%llu\n",Ans);
			}
		}
	}
	namespace solve2 {
		ull Ans[N];
		ull Now;
		inline void del1(int l,int r) {
			if(r<l)return;
			int Mx1=0,Mx2=0;
			F(i,l,r) {
				Max(Mx1,a[i]),Max(Mx2,b[i]);
				Now-=1ull*Mx1*Mx2;
			}
		}
		inline void del2(int r,int l) {
			if(r<l)return;
//		cerr<<"l="<<l<<" r="<<r<<"\n";
			int Mx1=0,Mx2=0;
			PF(i,r,l) {
				Max(Mx1,a[i]),Max(Mx2,b[i]);
				Now-=1ull*Mx1*Mx2;
			}
			Now+=Mx1*Mx2;
		}
		inline void put(int r,int l) {
			int Mx1=0,Mx2=0;
			PF(i,r,l) {
				Max(Mx1,a[i]),Max(Mx2,b[i]);
				Now+=1ull*Mx1*Mx2;
			}
		}
		void main() {
			sort(q+1,q+Q+1);
			int l=1,r=0;
			F(i,1,Q) {
//			cerr<<"l="<<l<<" r="<<r<<"\n"<<"ql="<<q[i].l<<" qr="<<q[i].r<<"\n";
				if(q[i].l>max(l,r)) {
					Now=0;
					l=q[i].l,r=q[i].l-1;
					while(r<q[i].r)put(++r,q[i].l);
				} else {
					while(l<q[i].l)del1(l++,q[i-1].r);
//			cerr<<"Now1="<<Now<<"\n";
					while(r>q[i].r) {
						del2(r--,q[i-1].l);
//				cerr<<"Now2="<<Now<<"\n";
					}
//			cerr<<"l="<<l<<" r="<<r<<"\n";
					while(r<q[i].r)put(++r,q[i].l);
//			cerr<<"Now3="<<Now<<"\n";
				}
				Ans[q[i].id]=Now;
			}
			F(i,1,Q)printf("%llu\n",Ans[i]);
		}
	}
	bool ending;
	int main() {
//	cerr<<1.0*(&ending-&beginning)/1024/1024<<"MB\n";
//	system("fc match.ans match3.ans");
//	freopen("match3.in","r",stdin);
//	freopen("match.ans","w",stdout);
		T=read(),n=read();
		F(i,1,n)a[i]=read();
		F(i,1,n)b[i]=read();
		Q=read();
		ll sum=0;
		F(i,1,Q)q[i].l=read(),q[i].r=read(),q[i].id=i,sum+=(q[i].r-q[i].l)*(q[i].r-q[i].l)/2;
		if(sum<=3e8)solve1::main();
		else solve2::main();
//solve1::main();
//	solve2::main();
		return 0;
	}
	inline int read() {
		int x=0;
		bool f=1;
		char c=getchar();
		while(!isdigit(c))f=c^45,c=getchar();
		while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
		return f?x:-x;
	}
}
bool ending;
int main() {
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	solve::main();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}
