#include<bits/stdc++.h>
#ifdef xay5421
#define D(...) fprintf(stderr,__VA_ARGS__)
#else
#define D(...) ((void)0)
#endif
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define each(x,v) for(auto&x:v)
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
using namespace std;
using LL=long long;
using ULL=unsigned long long;
template<class T>void rd(T&x){
	int f=0,c;
	while(!isdigit(c=getchar()))f^=!(c^45);
	x=(c&15);
	while(isdigit(c=getchar()))x=x*10+(c&15);
	if(f)x=-x;
}
const int N=250005;
int T,n,Q,ql[N];
ULL a[N],b[N],ans[N];
vector<int>V[N];
int now_t;
struct mat{
	ULL a[5][5];
	mat operator*(const mat&rhs)const{
		mat ret;
		rep(i,0,4)rep(j,0,4){
			ret.a[i][j]=0;
			rep(k,0,4)ret.a[i][j]+=a[i][k]*rhs.a[k][j];
		}
		return ret;
	}
};
struct vec{
	ULL a[5];
	vec operator*(const mat&rhs){
		vec ret;
		rep(i,0,4){
			ret.a[i]=0;
			rep(j,0,4){
				ret.a[i]+=a[j]*rhs.a[j][i]
			}
		}
		return 0;
	}
};
struct segtree{
	vec tr[N*4];
	mat tg[N*4];
	bool hav[N*4];
	void pst(int k1,const mat&k2){
		if(!hav[k1]){
			hav[k1]=1;
			tg[k1]=k2;
		}else{
			tg[k1]=tg[k1]*k2;
		}
	}
	void psd(int k1){
		if(hav[k1]){
			hav[k1]=0;
			pst(k1*2,tg[k1]);
			pst(k1*2+1,tg[k1]);
			hav[k1]=0;
		}
	}
	void add_a(int l,int r,ULL x){
		apply(1,1,n,l,r,(mat){{},{},{},{}});
	}
	void add_b(int l,int r,ULL x){
		apply(1,1,n,l,r,);
	}
	ULL ask(int k1,int k2,int k3,int k4,int k5){
		if(k2>k5||k3<k4)return 0;
		if(k4<=k2&&k3<=k5)return tr[k1].a[3];
		psd(k1);
		int mid=(k2+k3)>>1;
		return ask(k1*2,k2,mid,k4,k5)+ask(k1*2+1,mid+1,k3,k4,k5);
	}
}sgt;
int main(){
	freopen("match.in","r",stdin);
	freopen("match.out","w",stdout);
	rd(T),rd(n);
	rep(i,1,n)rd(a[i]);
	rep(i,1,n)rd(b[i]);
	rd(Q);
	rep(i,1,Q){
		int l,r;
		rd(l),rd(r);
		ql[i]=l;
		V[r].pb(i);
	}
	sgt.bud(1,1,n);
	vector<int>st1={0},st2={0};
	rep(i,1,n){
		while(SZ(st1)>1&&a[i]>a[st1.back()]){
			int r=st1.back();
			st1.pop_back();
			int l=st1.back();
			sgt.add_a(1,1,n,l+1,r,-a[r]);
		}
		while(SZ(st2)>1&&b[i]>b[st2.back()]){
			int r=st2.back();
			st2.pop_back();
			int l=st2.back();
			sgt.add_b(1,1,n,l+1,r,-b[r]);
		}
		{
			sgt.add_a(1,1,n,st1.back()+1,i,a[i]);
			st1.pb(i);
		}
		{
			sgt.add_b(1,1,n,st2.back()+1,i,b[i]);
			st2.pb(i);
		}
		++now_t;
		each(x,V[i]){
			ans[x]=sgt.ask(1,1,n,ql[x],i);
		}
	}
	rep(i,1,Q)printf("%llu\n",ans[i]);
	return 0;
}
